सभी संयोजनों को खोजने के लिए इस एल्गोरिदम की समय जटिलता क्या है?

Question

युग्म
को देखते हुए दो पूर्णांकों n और कश्मीर, 1 से बाहर कश्मीर संख्या के सभी संभव संयोजनों लौट ... एन।
उदाहरण के लिए, यदि n = 4 और कश्मीर = 2, एक समाधान है:

[ 
    [2, 4], 
    [3, 4], 
    [2, 3], 
    [1, 2], 
    [1, 3], 
    [1, 4], 
] 

---

निजी तौर पर मुझे लगता है कि,
समय जटिलता = O (n^ट), एन और कश्मीर हैं इनपुट।

---

सभी मदद के लिए धन्यवाद।
अंत में, समय जटिलता = ओ (सी (एन, के) * के) = ओ ((एन!/(के! * (एन - के)!)) * के), एन और के है इनपुट,
चूंकि, जब भी हम संयोजन प्राप्त करते हैं, हमें कॉपी सबलिस्ट सूची को एक_रेस्ट में कॉपी करने की आवश्यकता होती है, जो ओ (के), है सी (एन, के) * के।

---

सी ++

#include <vector> 
using namespace std; 

class Solution { 
public: 
    vector<vector<int> > combine(int n, int k) { 
     vector<vector<int>> list; 

     // Input validation. 
     if (n < k) return list; 

     int start = 1; 
     vector<int> subList; 
     helper(n, k, start, list, subList); 

     return list; 
    } 

    void helper(int n, int k, int start, 
       vector<vector<int>> &list, vector<int> &subList) { 
     // Base case. 
     if (subList.size() == k) { 
      vector<int> one_rest(subList); 
      list.push_back(one_rest); 
      return; 
     } 
     if (start > n) return; 

     for (int i = start; i <= n; i ++) { 
      // Have a try. 
      subList.push_back(i); 

      // Do recursion. 
      helper(n, k, i + 1, list, subList); 

      // Roll back. 
      subList.pop_back(); 
     } 
    } 
}; 

Answer 1

चूंकि आप सूचियों का उपयोग कर रहे हैं, push_back और pop_backO(1) संचालन हैं। साथ ही, आप एक बार एक वैध संयोजन उत्पन्न करना समाप्त कर देते हैं। इस प्रकार, जटिलता O(n choose k) है।

Answer 2

समय जटिलता संयोजन देखते हैं की संख्या के बराबर है।

इस मामले में यह n choose k है।

Answer 3

मुझे नहीं लगता कि यह ओ (एन^के) है। क्योंकि इसके बारे में सोचो। आइए एन = 100 और के = 2 मान लें। आपकी जटिलता के मुताबिक यह शक्ति 2 के लिए 100 होगा। लेकिन अगर यह एन = 100 और के = 10 है, तो यह 10 की शक्ति के लिए 100 होगा। लेकिन यदि आप इसके बारे में सोचते हैं, तो एन = 100 के साथ कहीं अधिक संयोजन हैं , एन = 100, के = 10 से के = 2। जटिलता वास्तव में वास्तविक सूत्र है: जो एन है!/(के! (एन-के)!)। और इसलिए जटिलता ओ (एन!/के! (एन-के) होगा!)।

Answer 4

जटिलता O(C(n,k)) है जो O(n choose k) है।

यह O(min(n^k, n^(n-k))) के बराबर होता है।