这2个程序的时间复杂度

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算法的典型例子.您应该使用StringBuilder它,这是构建字符串的正确方法.