算法打印字符串的排列 - 運行時間分析

我有下面的代碼來打印指定字符串的排列。 [爲了簡化和不丟失專注於什麼，我想，讓我們假設有沒有字符串中的字符複製]算法打印字符串的排列 - 運行時間分析

public static int count = 0; 

public static void permute(String soFar, String strLeft) { 

    if(strLeft.length() == 1) { 
     soFar += strLeft; 
     System.out.println(++count + " :: " + soFar); 
    } 

    for(int i=0; i<strLeft.length(); i++) { 
     permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1)); 
    } 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    String input = "abcd"; 
    permute("",input); 
}

我想弄清楚這個代碼的運行時間。

我至今思念鏈：想寫一個復發，

T(n) = n * T(n-1) + O(n) for n > 1 
    = 1     for n = 1

有n個！排列，但遞歸調用的次數大於n !.實際上，對於輸入字符串爲「abcd」的例子，即4個字符，排列函數的調用次數爲65.

任何關於如何查找此代碼的運行時間的指針？

來源

2013-03-05 Anurag Kapur

什麼是更大 - 電話給該方法的數字或數字的，它將其運行時的輸出量？ – Makoto 2013-03-05 02:15:34

重複/類似的問題？ http://stackoverflow.com/questions/11425344/what-is-the-complexity-big-o-of-this-algorithm – apnorton 2013-03-05 02:16:27

@anorton - 是的，這看起來像一個重複。謝謝！我正在通過另一個線程的答案，並將其標記爲已關閉。 – 2013-03-05 02:18:01

嗯，首先，你讓多餘的電話。如果只剩下一個字符，則會發出解決方案。但是，你仍然會用空字符串調用permute並破壞調用計數。

我的第一個改進是一個else添加到if條款。

public static void permute(String soFar, String strLeft) { 

    if(strLeft.length() == 1) { 
     soFar += strLeft; 
     System.out.println(++count + " :: " + soFar); 
    } 
    else { 
     for(int i=0; i<strLeft.length(); i++) { 
      permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1)); 
     } 
    } 
}

這減少了41的調用數量。並計算調用次數，構造調用樹並統計節點。當每個呼叫由從字符串去除一個字符進行，則有：
1通話長度爲4的，長度爲3的
4呼叫，長度爲2的
12呼叫和長度爲1的
24呼叫

其中總計爲41.Voilá。

來源

2013-03-05 07:43:09 alzaimar

謝謝。因此，一個大小爲n的問題的一般解決方案是：n！/ 1！ + n！/ 2！ + ... + n！/ n！ – 2013-03-06 02:36:45

我仍然不知道如何將上面的一般解決方案轉換成相應的Big-Oh，但是對於我來說理解一個表示問題或遞歸調用如何擴散的關係更重要。所以，對你的答案+1，我已標記爲接受。謝謝！ – 2013-03-06 02:38:38

不客氣。 – alzaimar 2013-03-06 10:33:11

算法打印字符串的排列 - 運行時間分析

回答

相關問題