简单字符串连接的时间复杂度

Question

以下方法的成本是多少。您如何计算？

public String joinWords(String[] words) {
    String sentence = "";
    for (String w : words) {
        sentence = sentence + word;
    }
    return sentence;
}

Answer 1

假设对于两个长度分别为r和s的字符串，字符串连接的开销为O（r + s）-历史上在Java but may change going forward中是这种情况-运行时间为O（mn），其中n为总数输入字符串中的字符数，m是输入字符串的数。

要看到这一点，请注意，如果字符串长度为n1，n2，...，n_m，则运行时将为

n1 +（n1 + n2）+（n1 + n2 + n3）+ ... +（n1 + n2 + ... + n_m）

= m（n_1）+（m-1）（n_2）+（m-2）（n-3）+ ... + n_m

= m（n_1 + n_2 + ... + n_m）-n_2-2n_3-3n_4-...-（m-1）n_m

受n_1 + ... + n_m = n的约束，当n_1 = n且所有其他值均为0时，此值最大化。在这种情况下，运行时间变为mn，因此运行时间为O（mn）。