java - 这两个程序的时间复杂度

Question

我是复杂性分析的新手。任务是给定一个像“Code”这样的非空字符串，返回一个像“CCoCodCode”这样的字符串。我有这两个程序在做同样的事情。

程序 1:

public String stringSplosion(String str) {
    String result = "";
    for (int i=0; i<str.length(); i++) {
        for(int j=0;j<=i;j++)
            result += str.charAt(j);
    }
    return result;
}

所以，上面的一个非常简单，这个程序有 O(n^2) 的复杂度。

程序 2:

public String stringSplosion(String str) {
    String result = "";
    // On each iteration, add the substring of the chars 0..i
    for (int i=0; i<str.length(); i++) {
        result = result + str.substring(0, i+1);
    }
    return result;
}

从另一个 StackOverflow 问题来看，str.substring() 的时间复杂度似乎为 O(n)。在这种情况下，程序 2 也具有 O(n^2) 时间复杂度。

我的分析是正确的还是遗漏了什么？

Answer 1

事实上，两者具有相同的复杂度 - O(n^3)。那是因为您正在使用 += 来连接答案!那里有一个你没有考虑到的隐藏循环，还有一个经典的例子 Schlemiel the Painter's Algorithm .您应该改用 StringBuilder，这是构建字符串的正确方法。