我从一本电子书中复制了这段文本。它说这个算法的复杂度是O(n2)，并给出了解释，但我不太理解。
问题：这段代码的运行时间是多少？
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
书中给出的答案是：
O(n2)，其中 n 是句子中字母的数量。原因如下：每次将一个字符串附加到句子末尾时，都会创建句子的副本并遍历句子中的所有字母以复制它们。如果每次在循环中最多需要遍历 n 个字符，并且你至少要循环 n 次，那么这将导致 O(n2) 的运行时间。糟糕！
有人能否更清楚地解释一下这个答案？
这似乎是一个误导性的问题，因为我刚刚看过那本书。书中的这部分文字是一个打印错误！以下是上下文：
===================================================================
问题：这段代码的运行时间是多少？
1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }
答案：O(n2)，其中n是句子中字母的数量。 原因在于：每次将字符串附加到句子时，都会创建句子的副本，并遍历句子中的所有字母以将它们复制过来。如果每次在循环中最多迭代n个字符，并且您至少要循环n次，则运行时间为O(n2)。痛苦啊！ 使用StringBuffer（或StringBuilder）可以帮助您避免这个问题。
1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }
你是否注意到作者搞混了吗？她提到的O(n2)解决方案（第一个）与“优化”后的方案（后面的那个）完全相同。所以，我的结论是作者试图呈现其他内容，例如每次附加下一个字符串时始终将旧句子复制到新缓冲区，作为O(n2)算法的示例。StringBuffer不应该如此愚蠢，因为作者还提到“使用StringBuffer（或StringBuilder）可以帮助您避免这个问题。”
针对这个高度抽象的代码，回答涉及复杂性的问题有一定难度。根据Java文档中的描述，append函数的复杂度没有明确保证。正如其他人所指出的那样，应当（也可以）将StringBuffer类编写为字符串添加的复杂度不依赖于StringBuffer当前持有的字符串长度。
然而，我怀疑仅仅告诉提问者“你的书是错的！”并没有太多帮助。我们应该看看做了哪些假设，并明确作者想要表达的意思。
您可以做出以下假设：
new StringBuffer 是 O(1)w 在 words 中是 O(1)sentence.toString 的复杂度最多为 O(n)。问题实际上是关于 sentence.append(w) 的顺序，这取决于它在 StringBuffer 内部的实现方式。幼稚的方法是像Shlemiel the Painter一样进行操作。
最后，还有一个实现方面的问题没有涉及到，那就是由教科书答案提出的内存分配问题。每次你想要往StringBuffer中添加更多的字符时，不能保证字符数组中有足够的空间来容纳新的单词。如果没有足够的空间，你的计算机需要先在一个清洁的内存区域中分配一些额外的空间，然后将旧的StringBuffer数组中的所有信息复制过去，然后才能像以前一样继续操作。像这样复制数据需要O(a)时间（其中a是要复制的字符数）。
在最坏的情况下，每次添加新单词时都必须分配更多的内存。这基本上把我们带回到了原点，使得循环的复杂度为O(n^2)，这也是书中所暗示的。如果假设没有什么疯狂的事情发生（单词不以指数增长的速度变长！），那么通过让分配的内存呈指数增长的方式，你可以将内存分配的数量减少到类似于O(log(n))的数量级。如果那是内存分配的数量，并且内存分配总体上是O(a)，那么循环中仅与内存管理有关的总复杂度就是O(n log(n))。由于添加操作的复杂度是O(n)，并且小于内存管理的复杂度，因此该函数的总复杂度为O(n log(n))。
同样，Java文档在StringBuffer容量增长的方式方面没有帮助我们，它只说“如果内部缓冲区溢出，则自动扩大”。根据扩大容量的方式，你可能会得到O(n^2)或O(n log(n))的总体复杂度。
作为留给读者的练习：找到一种简单的方法来修改该函数，使总体复杂度为O(n)，消除内存重新分配问题。
log(n)乘以n是具有误导性的，因为并非每个重新分配都具有相同的成本。最终的重新分配与所有其他重新分配的成本大致相同。 - fgbO(log(n) * log(n))，虽然我不确定这是否是一种有用的摊销思路。但它提醒我它可能接近于 O(n)，需要更深入地研究。在这种情况下，您大约会复制平均约log(n)个字符，大约重复log(n)次。 - ebyrob被接受的答案是错误的。 StringBuffer 具有摊销时间复杂度为 O(1) 的追加操作，因此 n 次追加的时间复杂度将为 O(n)。
如果它的追加操作不是 O(1)，那么 StringBuffer 就没有存在的理由，因为使用普通的 String 连接来编写那个循环也会产生 O(n^2) 的时间复杂度！
javac 实际上会优化字符串拼接以使用 StringBuilder。 - Mechanical snail我尝试使用这个程序进行检查
public class Test {
private static String[] create(int n) {
String[] res = new String[n];
for (int i = 0; i < n; i++) {
res[i] = "abcdefghijklmnopqrst";
}
return res;
}
private static String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
public static void main(String[] args) {
String[] ar = create(Integer.parseInt(args[0]));
long begin = System.currentTimeMillis();
String res = makeSentence(ar);
System.out.println(System.currentTimeMillis() - begin);
}
}
结果如预期的O(n)：
java Test 200000 - 128 毫秒
java Test 500000 - 370 毫秒
java Test 1000000 - 698 毫秒
版本 1.6.0.21
我认为书中的这段文字一定是个打印错误，我认为下面的内容才是正确的，我已经修改好了：
===================================================================
问题：这段代码的运行时间是多少？
public String makeSentence(String[] words) {
String sentence = new String("");
for (String w : words) sentence+=W;
return sentence;
}
答案：O(n2)，其中n是句子中字母的数量。原因是每次将一个字符串附加到sentence后，都会创建sentence的副本并遍历sentence中的所有字母以将它们复制过去。如果每次循环都需要迭代最多n个字符，并且至少要循环n次，那么这将给您带来O(n2)的运行时间。哎呀！使用StringBuffer（或StringBuilder）可以帮助您避免这个问题。
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
我是不是正确？
第一种情况：
public String makeSentence(String[] words) {
String sentence = new String();
for (String w : words) sentence += w;
return sentence;
}
复杂度 : O(n^2) -> (n个单词) x (每个迭代中复制的n个字符，用于将当前句子复制到StringBuffer中)
第二个案例 :
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
复杂度：O(n) -> (n 个单词) x O(1)（StringBuffer 连接的分摊复杂度）
/* StringBuffer is just a proxy */
public AbstractStringBuilder append(String str)
{
if (str == null) str = "null";
int len = str.length();
ensureCapacityInternal(count + len);
str.getChars(0, len, value, count);
count += len;
return this;
}
/* java.lang.String */
void getChars(char dst[], int dstBegin) {
System.arraycopy(value, offset, dst, dstBegin, count);
}
你的书要么过时，要么糟糕，或者两者兼而有之。我没有足够的决心去查找JDK版本以找到一个不那么优化的StringBuffer实现，但也许存在这样的实现。
System.arraycopy实现追加操作，而System.arraycopy又依赖于objArrayKlass.cpp中的O(n)操作（在OpenJDK分发中实现），以执行内存中数组对象成员的实际复制。因此，O(M*n)是正确的。我怀疑其他任何JVM都无法在常数时间内进行复制，因为占用的内存块必须重新对齐。 - Vineet Reynoldsn^2。
n*n 将是 n^2。在我看来，这似乎是 O(n)（其中 n 是所有单词中字母的总数量）。你基本上正在迭代 words 中的每个字符，并将其附加到 StringBuffer 中。
我唯一能想到这可能是 O(n^2) 的方式是如果 append() 在附加任何新字符之前迭代缓冲区中的所有内容。如果字符数超过当前分配的缓冲区长度（它必须分配一个新缓冲区，然后将当前缓冲区中的所有内容复制到新缓冲区中），则偶尔可能会发生这种情况。但这不会在每次迭代中发生，因此仍然不会产生 O(n^2)。
最多你会有O(m * n)，其中m是缓冲区长度增加的次数。由于每次分配更大的缓冲区时，StringBuffer将双倍增加其缓冲区大小，因此我们可以确定m大致等于log2(n)（实际上是log2(n) - log2(16)，因为默认初始缓冲区大小为16而不是1）。
因此，真正的答案是该书的示例为O(n log n)，通过预先分配足够容纳所有字母的StringBuffer，您可以将其降至O(n)。
+=追加字符串确实会展示出书中所描述的低效行为，因为它必须分配一个新的字符串并将两个字符串的所有数据复制到其中。因此，如果您这样做，它的时间复杂度是O(n^2)。String sentence = "";
for (String w : words) {
sentence += w;
}
但是使用StringBuffer不应该产生与上面示例中相同的行为。这也是StringBuffer存在的主要原因之一。
1 + 2 + 3 + ...... + n + n = 0.5n(n+1) + n
我使用等差数列求和公式得到了这个结果。
O(0.5n^2 + 1.5n) = O(n^2).
如果我们使用多字母单词，就会更少地找到StringBuffer的结尾，从而减少CPU时间，达到“更好”的情况。