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

Question

这是一个查找字符串的所有子字符串的解决方案。

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³)。

如有错误，请指正。

Answer 1

向字符串添加一个字符是一个复杂度为 O(1) 的操作。如果您还考虑到使用 println 打印输出所需的时间，您将获得 O(n³)。