java - 字符串时间复杂度

Question

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

Assume that the strings are all the same length (call this x) and that there are n strings. On each concatenation,a new copy of the string is created, and the two strings are copied over,character by character. The 1st iteration requires us to copy x characters. The second iteration requires copying 2x characters. The third iteration requires 3x ,and so on. The total time therefore is O(x + 2x + . . . + nx). This reduces to O(xn^2).

1) 我无法从书中的答案中理解他们如何在第三次迭代中获得 3x 个字符，在第四次迭代中获得 4x 个字符。 String 是不可变的，在每个句子变量赋值中都会创建新的 String 对象。然后是应该通过 char 复制字符串 char 的先前值和 w 的值。我又得到了 2x 个字符。谢谢你们 !

Answer 1

在第一次迭代中，sentence 有 0 个字符，w 有 x 个字符，所以你必须复制 x 个字符。

在第二次迭代中，sentence 有 x 个字符，w 有 x 个字符，所以你必须复制 2*x 个字符。

在第 3 次迭代中，sentence 有 2*x 个字符，w 有 x 个字符，所以你必须复制 3*x 个字符。

在第 4 次迭代中，sentence 有 3*x 个字符，w 有 x 个字符，所以你必须复制 4*x 个字符。

等等……