查找字符串的所有子字符串的複雜性

以下是查找字符串的所有子字符串的解決方案。查找字符串的所有子字符串的複雜性

for (int i = 0; i < str.length(); i++) { 
    String subStr; 
    for (int j = i; j < str.length(); j++) { 
     subStr = str + str.charAt(j)); 
     System.out.println(subStr); 
    } 
}

所有在互聯網上，我讀了這對代碼的複雜度爲O（n ）。但是+操作是O（n）操作。因此在我看來，複雜性應該是O（n ）。

如果我錯了，請糾正我的理解。

來源

2013-07-07 JavaDeveloper

請勿使用'+'。改用'StringBuilder'。 – Maroun

將字符添加到字符串是O（1）操作。如果考慮到需要打印輸出的時間爲println，則會得到O（n ）。

來源

2013-07-07 09:36:10

查找字符串的所有子是O（通過尋找一個子我的意思是確定其開始和結束索引）（N ），很容易看到，因爲子的總數是O（n ）。

但是打印所有這些出爲O（n 3 ），僅僅是因爲要被打印的字符的總數目爲O（n 3 ）。在您的代碼中，println增加了O（n）的複雜性（如果正確使用/實施，+運營商應該具有O（1）複雜性）。

來源

2013-07-07 09:36:20 Inspired

從一個字符串中找到所有的子串是一種天真的方式，的確是O（n^2）。但是問題中的代碼不可能這樣做。這是更正後的版本。

for (int i = 0; i < str.length(); ++i) { 
     //Initialize with max length of the substring 
     StringBuilder prefix = new StringBuilder(str.length() - i); 
     for (int j = i; j < str.length(); ++j) { 
      prefix.append(str.charAt(j)); //this step is O(1). 
      System.out.println(prefix); //this step is supposed to be O(1) 
     } 
    } 

The total number of iterations is given by 
Outer Loop : Inner Loop 
First time : n 
Second time : n - 1 
Third Time : n - 2 
.. 
n - 2 time : 2 
n - 1 time : 1 



So the total number of iterations is sum of iterations of outer loop plus sum of iterations of the inner loop. 
n + (1 + 2 + 3 + ... + n - 3 + n - 2 + n - 1 + n) is = O(n^2)

來源

2013-07-07 10:12:53 bsd

查找字符串的所有子字符串的複雜性

回答

相關問題