为什么这个字符串连接算法需要这么多步骤？

Question

基于《破解编码面试》一书（第 90 页）一书，以下算法需要 O(xn\xc2\xb2) 时间（其中“x”表示字符串的长度，“n”是字符串的数量） ）。代码是用Java编写的。有人能解释一下我们如何获得这样的运行时间吗？

\n\n

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

\n

Answer 1

对于连接到 的每个字符串sentence，都会创建一个新字符串StringBuilder，使用该方法将两个字符串附加到该字符串StringBuilder.append，然后使用该方法创建结果字符串StringBuilder.toString。此操作的复杂度为 O(n_1 + n_2)，其中 n_1 和 n_2 是字符串的长度。

在此代码中，循环运行 n 次，每次运行时，长度sentence为 O(xn) 的字符串与长度为 x 的字符串连接起来w。因此，正如预期的那样，总体复杂度为 n * O(xn + x) = O(xn^2)。

对于怀疑者，这里是该joinWords方法的反汇编字节码；我使用 10.0.1 编译它javac（这是我目前必须提供的版本）。StringBuilder 在循环内部的位置 25 到 41 中使用（请参阅 参考资料48: goto 12）。

  java.lang.String joinWords(java.lang.String[]);
    Code:
       0: ldc           #2                  // String
       2: astore_2
       3: aload_1
       4: astore_3
       5: aload_3
       6: arraylength
       7: istore        4
       9: iconst_0
      10: istore        5
      12: iload         5
      14: iload         4
      16: if_icmpge     51
      19: aload_3
      20: iload         5
      22: aaload
      23: astore        6
      25: new           #3                  // class java/lang/StringBuilder
      28: dup
      29: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      32: aload_2
      33: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      36: aload         6
      38: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      41: invokevirtual #6                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      44: astore_2
      45: iinc          5, 1
      48: goto          12
      51: aload_2
      52: areturn