arrays - 以下哪个代码的时间复杂度较小？请说明如何计算

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)

• 外循环执行n次数，内循环执行nums_subset = 2^n次数。

  

---

回溯方法：

• 又sort是O(n log n)

• 每次genSubsets调用都会循环nums.size() - start多次，每次执行一次递归调用，循环次数少 1 次。

  

---

哪个更大？由斯特林近似，

所以回溯成本更高。