Calulating我的程序的大O的複雜性

我的程序打印有雙字母例如在一個字一個字的所有排列「Helloo」Calulating我的程序的大O的複雜性

其結果將是： [heloo，直升機，你好，helloo]

private List<String> doubleLetterPermute(String start, String ending, List<String> possibleWords) { 
    String prev = ""; 
    for (int i = 0; i < ending.length(); i++) { 
     String letter = String.valueOf(ending.charAt(i)); 
     // its a double letter 
     if (letter.equals(prev)) { 
      doubleLetterPermute(start + ending.substring(0, i), ending.substring(i + 1), possibleWords); 
      doubleLetterPermute(start + ending.substring(0, i + 1), ending.substring(i + 1), possibleWords); 
     } 
     prev = letter; 
    } 
    possibleWords.add(start + ending); 
    return possibleWords; 
}

我不知道如何計算的複雜性，當遞歸函數進來，它循環n次，其中n是一個字的字符數，爲O（n），但我在每一次出現雙字母的時候都會分裂這個詞，那麼這個詞怎麼會在大的範圍內顯示O符號？

來源

2013-04-22 Decrypter

用於置換的Big-O通常是O（n！），請參見[本頁]（http://www.daveperrett.com/articles/2010/12/07/comp-sci-101-big-o-符號/）作爲參考 – 2013-04-22 20:27:55

爲了計算您的複雜性，您需要查看最差和最好的情況。

充其量，你會有一個長度爲N的字，沒有雙字母，比方說「abcde」。您的複雜度爲O（n），因爲您只有一個大小爲N的環。

最糟糕的情況是，您需要用同一個字母表示長度爲N的字，比如說「aaaaa」。在這種情況下，您有一個大小爲N的循環，其中包含2個大小爲（N - i）的循環。所以，複雜度爲O（2（n-i）* n）或O（n^2）。

來源

2013-04-22 19:29:42 Kimko

謝謝Kimko。在給出最終的大O結果時，你會採取最壞還是最好的情況？ – Decrypter 2013-04-22 20:26:06

@大O分析器你**總是**最壞的情況。在這種情況下，它看起來像O（2^n）時間分析。 – 2013-04-22 20:33:26

Calulating我的程序的大O的複雜性

回答

相關問題