排列函數的運行時間

我的書爲計算一個唯一字符串（見下面的代碼）的所有排列的函數提供以下代碼，並且說運行時間是O（n！），「因爲那裏是n！排列組合。「排列函數的運行時間

我不明白他們如何計算運行時間爲O（n！）。我假設他們的意思是「n」是原始字符串的長度。我認爲運行時間應該是O（（n + 1）XY），因爲getPerms函數將被調用（n + 1）次，並且X和Y可以表示外循環和內循環的運行時間分別。有人可以向我解釋爲什麼這是錯誤的/書的答案是正確的？

謝謝。

public static ArrayList<String> getPerms(String str) 
{ 
    if (str == null) 
     return null; 

    ArrayList<String> permutations = new ArrayList<String>(); 

    if (str.length() == 0) 
     permutations.add(""); 
     return permutations; 

    char first = str.charAt(0); //first character of string 
    String remainder = str.substring(1); //remove first character 

    ArrayList<String> words = getPerms(remainder); 
    for (String word: words) 
    { 
     for (i = 0; i <= word.length(); i++) 
     { 
      String s = insertCharAt(word, first, i); 
      permutations.add(s) 
     } 
    } 

    return permutations; 

} 

public static String insertCharAt(String word, char c, int j) 
{ 
    String start = word.substring(0, i); 
    String end = word.substring(i); 
    return start + c + end; 
}

來源：開裂的編碼訪談

來源

2015-05-20 randomUser47534

@shekharsuman也就是說在書中提供的唯一代碼。我同意它不完整。 – randomUser47534

從我們的直覺來看，顯然沒有現有算法可以生成N項的排列，這些項的表現比O（n！）好，因爲有n！可能性。

由於gePerm(n)其中n是一個長度爲n的字符串將調用getPerm(n-1)，您可以將遞歸代碼減少到遞歸等式中。然後，我們使用它返回的所有值，並放置一個循環N次的內部循環。因此，我們有

P _ň =爲nP _N-1
P = 1

這是很容易看到將P _ñ = N！通過伸縮方程。

如果你有困難的時候想象我們是如何想出這個公式，你也可以認爲這種方式

ArrayList<String> words = getPerms(remainder); 
for (String word: words)       // P(n-1) 
{ 
    for (i = 0; i <= word.length(); i++)   // nP(n-1) 
    { 
     String s = insertCharAt(word, first, i); 
     permutations.add(s) 
    } 
}

來源

2015-05-20 07:40:53 invisal

N元素的排列的計數是N * (N - 1) * (N - 2) * ... * 2 * 1，即N!。

第一個字符可以是任何一個N個字符。下一個字符可以是剩餘的N - 1個字符之一。現在我們已經有N * (N - 1)個案例。

因此，繼續我們將在每個步驟有N * (N - 1) * (N - 2) * ...個案。

因爲N元素排列的計數是N!，所以沒有一個實現可以比N！更快地排列長度爲N的數組。

來源

2015-05-20 06:43:44

謝謝。你能否解釋一下你的句子：「第一個字符可以是N個字符中的任何一個」？我認爲這本書把「第一個字符」只是字符串開頭的字符。因此，我認爲第一個字符只能是一個可能的字符，而不是N個字符中的任何一個？ – randomUser47534

看看字符串「123」的簡短例子。該實現修復了第一個字符'1'，然後遞歸調用自己並接收字符串「23」和「32」。然後它將第一個字符插入這些字符串的所有可能位置：第一個字符串爲「123」，「213」，231「，第二個字符串爲」132「，」312「，」321「。其實。 –

排列函數的運行時間

回答

相關問題