查找字符串的所有子字符串的复杂性

问题描述：

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 ）。

如果我错了，请纠正我的理解。

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

答

将字符添加到字符串是O（1）操作。如果考虑到需要打印输出的时间为println，则会得到O（n ）。

答

查找字符串的所有子是O（通过寻找一个子我的意思是确定其开始和结束索引）（N ），很容易看到，因为子的总数是O（n ）。

但是打印所有这些出为O（n 3 ），仅仅是因为要被打印的字符的总数目为O（n 3 ）。在您的代码中，println增加了O（n）的复杂性（如果正确使用/实施，+运营商应该具有O（1）复杂性）。

答

从一个字符串中找到所有的子串是一种天真的方式，的确是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)

查找字符串的所有子字符串的复杂性

相关推荐