Lesquels des codes suivants ont une complexité temporelle moindre? S'il vous plaît expliquer comment le calculer

Question

Voici le code pour le calcul des sous-ensembles d'un tableau donné:

1. Bit Manipulation Méthode: Comment analyser?

   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. Backtracking Méthode: Comment l'analyser

    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

opérations vectorielles: - push_back et pop_back sont à la fois O(1) - Constructeur avec l'argument de la taille n est O(n)

---

Bit procédé de manipulation:

• sort est O(n log n)
• Construction de res est O(nums_subset) = O(2^n)

• boucle extérieure est exécuté n fois, interne par nums_subset = 2^n fois.

  

---

méthode Backtracking:

• Encore une fois, sort est O(n log n)

• Chaque appel boucles genSubsets par nums.size() - start fois, chaque fois effectuer un appel récursif avec 1 boucle en moins.

  

---

Ce qui est plus grand? Par approximation de Stirling,

Alors Backtracking est plus coûteux.