根据《破解编码采访》（第90页）一书，以下算法需要O（xn²）时间（其中“ x”代表字符串的长度，“ n”代表字符串）。该代码使用Java。谁能解释一下我们如何获得这种运行时？
String joinWords(String[] words)
{
String sentence = "";
for(String w : words)
{
sentence = sentence + w;
}
return sentence;
}
为什么此字符串连接算法需要这么多步骤？
•
问答
lxmforyou 回答：为什么此字符串连接算法需要这么多步骤？
对于连接到StringBuilder的每个字符串，将创建一个新的StringBuilder.append，使用StringBuilder.toString方法将两个字符串附加到其后，然后使用sentence方法。此操作的复杂度为O（n_1 + n_2），其中n_1和n_2是字符串的长度。
在此代码中，循环运行n次，并且每次运行时，长度为O（xn）的字符串w与长度为x的字符串joinWords连接在一起。因此，总的复杂度是n * O（xn + x）= O（xn ^ 2），如预期的那样。
对于那些怀疑论者来说，这是javac方法的反汇编字节码；我使用48: goto 12 10.0.1（现在是我必须提交的版本）进行了编译。在循环内的第25到41位使用StringBuilder（请参见 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
）。
j