क्यों क्रमपरिवर्तन समारोह की समय जटिलता ओ (एन!)

Question

निम्नलिखित कोड पर विचार करें।

public class Permutations { 
    static int count=0; 
    static void permutations(String str, String prefix){ 
     if(str.length()==0){ 
      System.out.println(prefix); 
     } 
     else{ 
      for(int i=0;i<str.length();i++){ 
       count++; 
       String rem = str.substring(0,i) + str.substring(i+1); 
       permutations(rem, prefix+str.charAt(i)); 
      } 
     } 

    } 
    public static void main(String[] args) { 
     permutations("abc", ""); 
     System.out.println(count); 
    } 

} 

यहाँ तर्क, मुझे लगता है कि पीछा किया जाता है है- यह एक संभव उपसर्ग के रूप में स्ट्रिंग के प्रत्येक चरित्र मानता है और शेष n-1 पात्रों permutes।
तो द्वारा इस तर्क आवर्तन संबंध बाहर आता है

T(n) = n(c1 + T(n-1))   // ignoring the print time 

जो स्पष्ट रूप से हे है होना करने के लिए (एन!)। लेकिन जब मैंने एक काउंटर वैरिएबल का उपयोग किया ताकि देखने के लिए कि wheather algo वास्तव में n के क्रम में बढ़ता है, मुझे अलग-अलग परिणाम मिलते हैं। गिनती ++ (लूप के अंदर के अंदर) के लिए 2-लंबाई स्ट्रिंग के लिए
गिनती के 3-लंबाई स्ट्रिंग मान के लिए 4 गुना चलता है और 4 और 5-लंबाई के लिए इसकी 64 और 325 स्ट्रिंग होती है।
इसका मतलब है कि यह एन से भी बदतर हो जाता है !। तो क्यों कहा गया कि यह (और इसी तरह के अल्जी जो पारगम्य उत्पन्न करते हैं) रन समय के मामले में ओ (एन!) हैं।

Answer 1

लोग कहते हैं कि इस एल्गोरिथ्म O(n!) क्योंकि वहाँ n! क्रमपरिवर्तन रहे हैं, लेकिन क्या तुम यहाँ गिनती कर रहे हैं (एक अर्थ में) कर रहे हैं फ़ंक्शन को कॉल - और वहाँ n! की तुलना में अधिक फ़ंक्शन कॉल कर रहे हैं:

• जब str.length() == n, आप n कॉल करें;
• इनमें से प्रत्येक के लिए nstr.length() == n - 1 के साथ कॉल करता है, तो आप n - 1 कॉल करते हैं;
• इनमें से प्रत्येक n * (n - 1)str.length() == n - 2 के साथ कॉल करता है आप n - 2 कॉल करते हैं;
• ...

आप str.length() == k साथ n!/k! कॉल करते हैं, और के बाद से str.length()0 से n को जाता है, कॉल की कुल संख्या है:

राशि _{k = 0। .. एन} (एन!/के!) = एन! योग _{k = 0 ... n} (1/कश्मीर!)

लेकिन जैसा कि आप जानते हो सकता है:

राशि _{k = 0 ... + ऊ} 1/कश्मीर! = ई = ई

तो बुनियादी तौर पर, इस राशि, हमेशा स्थिर e (और अधिक से अधिक 1) से कम है तो आप कह सकते हैं कि कॉल की संख्या O(e.n!) जो O(n!) है।

रनटाइम जटिलता अक्सर सैद्धांतिक जटिलता से अलग है - सैद्धांतिक जटिलता में, लोगों को क्रमपरिवर्तन की संख्या पता करने के लिए क्योंकि एल्गोरिथ्म शायद इन क्रमपरिवर्तन की प्रत्येक जांच करने के लिए जा रहा है चाहता हूँ (इसलिए प्रभावी रूप से n! जांच किया जाता है), लेकिन वास्तव में बहुत कुछ चल रहा है।

_{यह सूत्र वास्तव में आप एक मूल्यों आप मिल की तुलना में, क्योंकि आप पहले समारोह कॉल जब str.length() == n गिनती नहीं दे देंगे।}

Answer 2

इस जवाब मेरे जैसे लोग हैं, जो ई = 1/0 याद नहीं है के लिए है! +1/1! +1/2! +1/3! ...

मैं समझा सकता है एक सरल उदाहरण का उपयोग करते हुए, कहते हैं कि हम "abc"

 // \  <--- for first position, there are 3 choices 
     /\ /\ /\ <--- for second position, there are 2 choices 
    /\/\/\ <--- for third position, there is only 1 choice 

के सभी परिवर्तन चाहते हैं तो ऊपर प्रत्यावर्तन का पेड़ है, और हम जानते 3!पत्र-गांठ जो "abc" के सभी संभव क्रमपरिवर्तन का प्रतिनिधित्व करता है देखते हैं, (जो भी है, जहां यह है कि हम print() परिणाम पर कोई क्रिया) यानी, है, लेकिन जब से तुम सभी समारोह कॉल की गणना कर रहे हैं, हम कुल (पत्ता + आंतरिक)

में कितने पेड़ नोड्स पता करने की जरूरत है अगर यह एक पूरा द्विआधारी पेड़ था, हम पता है 2^n पत्ता नोड्स ... कितने आंतरिक नोड्स हैं?

x = |__________leaf_____________|------------------------| 
let this represent 2^n leaf nodes, |----| represents the max number of 
nodes in the level above, since each node has 1 parent, 2nd last level 
cannot have more nodes than leaf 
since its binary, we know second last level = (1/2)leaf 
x = |__________leaf_____________|____2nd_____|-----------| 
same for the third last level...which is (1/2)sec 
x = |__________leaf_____________|____2nd_____|__3rd_|----| 

एक्स पेड़ नोड्स की कुल संख्या का प्रतिनिधित्व करने के लिए इस्तेमाल किया जा सकता है, और के बाद से हम हमेशा प्रारंभिक |-----| पर आधा काट रहे हैं हम जानते हैं कि कुल < = 2 * पत्ती

अब

क्रमचय पेड़

के लिए

x = |____leaf____|------------| 
let this represent n! leaf nodes 
since its second last level has 1 branch, we know second last level = x 
x = |____leaf____|____2nd_____|-------------| 
but third last level has 2 branches for each node, thus = (1/2)second 
x = |____leaf____|____2nd_____|_3rd_|-------| 
fourth last level has 3 branches for each node, thus = (1/3)third 
x = |____leaf____|____2nd_____|_3rd_|_4|--| | 
| | means we will no longer consider it 

यहाँ

हम देखते हैं कि कुल < 3 * पत्ती, इस आशा की जाती है के रूप में (ई = 2.718)