以下哪個代碼的時間複雜度較低？請解釋如何計算呢

Question

以下是計算給定數組的子集的代碼：

1. 位操作方法：如何分析呢？

   vector<vector<int>> subsets(vector<int>& nums) 
       { 
       sort(nums.begin(), nums.end()); 
   
       int num_subset = pow(2, nums.size()); 
       vector<vector<int> > res(num_subset, vector<int>()); 
   
       for (int i = 0; i < nums.size(); i++) 
        for (int j = 0; j < num_subset; j++) 
         if ((j >> i) & 1) 
          res[j].push_back(nums[i]); 
   
       return res; 
       } 
   

2. 回溯方法：如何分析它

    vector<vector<int>> subsets(vector<int>& nums) 
        { 
        sort(nums.begin(), nums.end()); // sort the original array 
        vector<vector<int>> subs; 
        vector<int> sub; 
        genSubsets(nums, 0, sub, subs); 
        return subs; 
        } 
   
       void genSubsets(vector<int>& nums, int start, vector<int>& sub,vector<vector<int>>& subs) 
        { 
        subs.push_back(sub); 
        for (int i = start; i < nums.size(); i++) { 
        sub.push_back(nums[i]); 
        genSubsets(nums, i + 1, sub, subs); 
        sub.pop_back(); 
        } 
       } 
   

Answer 1

向量運算： - push_back和pop_back都是O(1) - 構造與尺寸參數n是O(n)

---

位操作方法：

• sort是O(n log n)
• 的res施工O(nums_subset) = O(2^n)

• 外環由nums_subset = 2^n倍執行n倍，內。

  

---

回溯方法：

• 再次，sort是O(n log n)

• 每個genSubsets呼叫通過nums.size() - start次循環，每次執行遞歸調用1個較少的循環。

  

---

哪個更大？由斯特靈公式，

所以回溯是更昂貴。