इस कोड की जटिलता क्या होगी?

Question

मेरे कोड है:

vector<int> permutation(N); 
vector<int> used(N,0); 

void try(int which, int what) { 
    // try taking the number "what" as the "which"-th element 
    permutation[which] = what; 
    used[what] = 1; 

    if (which == N-1) 
    outputPermutation(); 
    else 
    // try all possibilities for the next element 
    for (int next=0; next<N; next++) 
    if (!used[next]) 
    try(which+1, next); 

    used[what] = 0; 
} 

int main() { 
    // try all possibilities for the first element 
    for (int first=0; first<N; first++) 
    try(0,first); 
} 

मैं कुछ वेबसाइट है, जहां मैं इस कोड में आए से जटिलता सीख रही थी। मेरी समझ के अनुसार, निम्नलिखित पंक्ति एन बार पुनरावृत्त करती है। तो जटिलता ओ (एन) है।

for (int first=0; first<N; first++) 

अगला मैं रिकर्सिव कॉल पर विचार कर रहा हूं।

for (int next=0; next<N; next++) 
    if (!used[next]) 
    try(which+1, next); 

तो, यह पुनरावर्ती कॉल कदम शामिल = टी (एन) की संख्या = Nc + टी (0)। (कुछ निरंतर कदम जहां है) वहाँ हम कह सकते हैं कि इस चरण के लिए, जटिलता है = ओ (एन)।

इस प्रकार कुल जटिलता है - ओ (N.N) = हे (एन^2)

मेरी समझ सही है? धन्यवाद!

Answer 1

इस एल्गोरिदम की जटिलता ओ (एन!) है (या यहां तक ​​कि ओ (एन! * एन) यदि outputPermutation ओ (एन) लगता है जो संभव लगता है)।

यह एल्गोरिदम 0 पुनर्नवीनीकरण के बिना प्राकृतिक संख्याओं के सभी क्रमपरिवर्तनों को आउटपुट करता है।

पुनरावर्ती क्रिया try ही क्रमिक रूप से स्थिति which में एन तत्वों डाल करने के लिए कोशिश करता है और प्रत्येक की कोशिश के लिए यह रिकर्सिवली, अगले which पद के लिए खुद का आह्वान तक which तक पहुँच जाता है N-1। इसके अलावा, प्रत्येक पुनरावृत्ति के लिए try वास्तव में (एन - which) बार आक्रमण किया जाता है, क्योंकि प्रत्येक स्तर पर दो तत्वों को पुनरावृत्ति को खत्म करने के लिए used के रूप में चिह्नित किया जाता है। इस प्रकार एल्गोरिदम एन * (एन -1) * (एन -2) ... 1 कदम लेता है।

Answer 2

यह एक पुनरावर्ती कार्य है। फ़ंक्शन "आज़माएं" खुद को रिकर्सिव रूप से कॉल करता है, इसलिए मुख्य() में लूप है(), लूप() में एक लूप, रिकर्सिव कॉल में एक लूप(), कोशिश करने के लिए अगले रिकर्सिव कॉल में लूप() और इसलिए पर।

आपको यह फ़ंक्शन क्या सावधानीपूर्वक विश्लेषण करने की आवश्यकता है, या आपको पूरी तरह से गलत परिणाम मिलेगा (जैसा आपने किया था)। आप वास्तव में इस कोड को एन = 1 से 20 के मानों के साथ और समय को मापने पर विचार कर सकते हैं। आप देखेंगे कि यह निश्चित रूप से ओ (एन^2) नहीं है। असल में, एन के किसी भी मूल्य को न छोड़ें; आप देखेंगे क्यों।