以這種方式查找排列的複雜性是什麼？

Question

此方法：

private static void permutation(String prefix, String str) 
{ 
    int n = str.length(); 
    if(n==0) 
    System.out.println(prefix); 
    else 
    { 
    for(int i=0;i<n;i++) 
     permutation(prefix+str.charAt(i),str.substring(0,i)+str.substring(i+1,n)); 
    } 
} 

發現字符串的所有排列。當permutation("","ABC"); 調用它打印：

ABC 
ACB 
BAC 
BCA 
CAB 
CBA 

現在的問題是：什麼是這種方法的複雜性？是O(n!)還是O(nlogn)。復發樹的答案將非常有幫助！謝謝，

Answer 1

第一次嘗試

既然你是印刷每個排列的n -string的和有這樣n!串，時間複雜度出現O(n!)。

復發，可以形象地顯示（不完整，但你應該明白我的意思），如下所示：

   -------------- p("", "ABC")------------ 
      /    |     \ 
     p("A", "BC")  p("B", "AC")  p("C", "AB") 
     |   | 
p("AB", "C") p("AC", "B") 
     |    | 
p("ABC", "")  p("ACB", "") 

正如你所看到的，調用樹的葉子具有所需的排列的形式prefix您打印在基本情況下。由於此樹中的樹葉數量爲n!，因此複雜度爲出現O(n!)。

爲什麼它不是（低至）O(nlogn)的直觀推理是O(nlogn)的其他重複看起來不像這樣。例如，在合併排序的情況下，您將問題大小減半並在每個步驟中執行線性合併操作。由於有log(n)步驟，因此您得到O(nlog(n))作爲重複的解決方案。然而，在這個問題中，由於你必須做更多的工作，所以時間複雜度更高。

更新在首次嘗試分析評論

後上面是不完全正確。這裏還有更多。確實呼叫樹有n!樹葉。但爲了達到這些葉子，我們必須在代表遞歸調用的每個非葉節點上做更多的工作。對於具有n字符的字符串str，第一級中的節點數顯然爲n。在進行下一次遞歸調用之前，還會進行字符串連接。這些使得它更耗時。每個n呼叫最終會附加總共至少n個字符。

在第二級，這些n節點中的每一個節點都會產生(n-1)節點，總共得到n(n-1)。同樣，有很多字符串連接。

這個過程會一直繼續，直到遞歸調出n!樹葉爲止。在調用樹節點的總數是

= n + n(n-1) + n(n-1)(n-2) + ... + n(n-1)(n-2)...1 
= n(n-1)(n-2)...1 + n(n-1)(n-2)...2 + n(n-1)(n-2)...3 + ... + n(n-1) + n 
= n! + (n!/2) + (n!/(2.3)) + ... + (n!/(1.2.3...(n-1)) --- these are n terms 
= n! (1 + 1/2 + 1/2.3 + 1/2.3.4 + ...) 
= n! (1.71828...) 
= O(n!) 

在每種這些調用的，至少有n字符被附加（以及如保羅指出，正在打印一個新的生產線），總量工作是O(n.n!)。

Answer 2

既不:-)

設T（N，K）是採取置換的調用步驟的數量，其中k是的str長度。顯然，T（n，0）= O（n）。我們有k個執行循環體，每個執行一些字符串concatenation（耗費O（n））和一個遞歸調用T（n，k-1）。因此，

T(n,k) = k (O(n) + T(n,k-1)). 

一個簡單的方法來猜測這復發的封閉形式寫出來幾個方面：

T(n,k) = k * (n + (k-1) * (n + T(n,k-2))) 

可以單獨所有這些n項：

 = kn + k(k-1)n + k(k-1)T(n,k-2) 

擴大多一點

 = kn + k(k-1)n + k(k-1)(k-2)n + k(k-1)(k-2)T(n,k-3) 

這表明

T(n,k) = kn + k(k-1)n + k(k-1)(k-2)n + ... + k!n 
     = n (k + k(k-1) + k(k-1)(k-2) + ... + k!) 

和

T(n,n) = n (n + n(n-1) + n(n-1)(n-2) + ... + n!) 
     = nn! (1/(n-1)! + 1/(n-2)! + 1/(n-3)! + ... + 1) 
      \----------------- --------------------/ 
           \/
          1 < x < 2 

因此T（N，N）= O（NN！）