4

Here is a solution for finding all substrings of a string.

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);
    }
}

All over the internet I read that the complexity of this code is O(n2). However the + operation is an O(n) operation. Thus in my opinion the complexity should be O(n3).

In case I am wrong, please correct my understanding.

4

3 回答 3

1

将字符添加到字符串是 O(1) 操作。如果您还考虑使用 打印输出所需的时间，您将得到 O(n 3println ) 。

于 2013-07-07T09:36:10.753 回答
1

查找字符串的所有子字符串是 O(n 2 )（通过查找子字符串我的意思是确定它的开始和结束索引），很容易看出，因为子字符串的总数是 O(n 2 )。

但是将它们全部打印出来是 O(n 3 )，因为要打印的字符总数是 O(n 3 )。在您的代码中，println增加了 O(n) 复杂度（+如果使用/实施得当，运算符应该具有 O(1) 复杂度）。

于 2013-07-07T09:36:20.383 回答
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)
于 2013-07-07T10:12:53.227 回答