我正在从我拥有的电子书中粘贴此文本。它说明了 O(n 2 ) 的复杂性并给出了解释，但我看不出如何。
问题：这段代码的运行时间是多少？
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
书中给出的答案：
O(n 2 )，其中 n 是句子中的字母数。原因如下：每次将字符串附加到句子时，都会创建句子的副本并遍历句子中的所有字母以将它们复制过来如果每次在循环中必须迭代最多 n 个字符，那么循环至少 n 次，这给了你 O(n 2 ) 的运行时间。哎哟!
有人可以更清楚地解释这个答案吗？
这似乎是一个误导的问题，因为我刚才碰巧读了那本书。书中这部分文字是错字！这是上下文：
==================================================== ==================
问题：这段代码的运行时间是多少？
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(n 2 )，其中 n 是句子中的字母数。原因如下：每次将字符串附加到句子时，都会创建句子的副本并遍历句子中的所有字母以复制它们。如果您必须在循环中每次迭代最多 n 个字符，并且您至少循环 n 次，那么这会给您一个 O(n 2 ) 运行时间。哎哟! 用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(n 2 ) 解决方案（第一个）与“优化”的解决方案（后者）完全相同。所以，我的结论是作者试图渲染其他东西，例如在附加每个下一个字符串时总是将旧句子复制到新缓冲区，作为 O(n 2 ) 算法的示例。StringBuffer 不应该这么傻，因为作者也提到了“使用 StringBuffer（或 StringBuilder）可以帮助你避免这个问题”。
当以抽象出实现细节的高层次编写时，要回答有关此代码复杂性的问题有点困难。Java 文档似乎没有就函数的复杂性提供任何保证append。正如其他人指出的那样，StringBuffer可以（并且应该）编写该类，以便附加字符串的复杂性不取决于StringBuffer.
但是，我怀疑问这个问题的人简单地说“你的书错了！”并没有太大帮助。- 相反，让我们看看正在做出什么假设，并弄清楚作者试图说什么。
您可以做出以下假设：
new StringBuffer是 O(1)w是wordsO(1)sentence.toString最多为 O(n)。问题实际上是 的顺序是什么sentence.append(w)，这取决于它在StringBuffer. 天真的方法是像Shlemiel the Painter那样做。
假设您使用 C 风格的以空字符结尾的字符串作为StringBuffer. 找到这样一个字符串结尾的方法是逐个读取每个字符，直到找到空字符 - 然后附加一个新字符串 S，您可以开始将字符从 S 复制到StringBuffer字符串（以另一个空字符结尾特点）。如果append这样写，就是 O( a + b )，其中a是当前在 中的字符数StringBuffer，而b是新单词中的字符数。如果你遍历一个单词数组，并且每次你必须在添加新单词之前读取你刚刚添加的所有字符，那么循环的复杂度是 O(n^2)，其中 n 是字符总数在所有单词中（也是最后一句中的字符数）。
另一方面，假设 的内容StringBuffer仍然是一个字符数组，但我们还存储了一个整数size，它告诉我们字符串有多长（字符数）。现在我们不再需要读取每个字符StringBuffer来找到字符串的结尾；我们可以在数组中查找索引size，它是 O(1) 而不是 O( a )。那么这个append函数现在只依赖于被附加的字符数，O( b )。在这种情况下，循环的复杂度为 O(n)，其中 n 是所有单词中的字符总数。
最后，实现的另一个方面还没有涉及，那就是教科书中的答案实际提出的方面——内存分配。每次你想写更多字符到你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)。
接受的答案是错误的。StringBuffer已摊销 O(1) 追加，因此n追加将是 O( n )。
如果不是 O(1) 追加，StringBuffer就没有理由存在，因为用普通String连接编写循环也将是 O( n ^2)！
我试图用这个程序检查它
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 测试 200000 - 128 毫秒
java 测试 500000 - 370 毫秒
java 测试 1000000 - 698 毫秒
版本 1.6.0.21
我认为书中的这些文字一定是错字，我认为正确的内容如下，我修复它：
==================================================== ==================
问题：这段代码的运行时间是多少？
public String makeSentence(String[] words) {
String sentence = new String("");
for (String w : words) sentence+=W;
return sentence;
}
答案：O(n 2 )，其中 n 是句子中的字母数。原因如下：每次将字符串附加到句子时，都会创建句子的副本并遍历句子中的所有字母以复制它们。如果您必须在循环中每次迭代最多 n 个字符，并且您至少循环 n 次，那么这会给您一个 O(n 2 ) 运行时间。哎哟! 用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 words) 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 words) x O(1)（StringBuffer 连接的摊销复杂度）
这真的取决于StringBuffer. 假设.append()是常数时间，很明显你有一个O(n)算法在时间 where n = length of the words array。如果.append 不是恒定时间，则需要将 O(n) 乘以该方法的时间复杂度。如果确实当前实现StringBuffer逐个字符地复制字符串，那么上面的算法是
Θ(n*m), 或O(n*m), 哪里n是字数,m是平均字长, 你的书是错的。我假设您正在寻找一个严格的界限。
书上答案不正确的简单例子：
String[] words = ['alphabet']根据书上的定义，n=8，所以算法将被 64 步限制。是这样吗？显然不严格。我看到有 n 个字符的 1 个分配和 1 个复制操作，所以你得到了大约 9 个步骤。O(n*m)如上所示，这种行为是由 的边界预测的。
我做了一些挖掘，这显然不是一个简单的角色副本。看起来内存正在被批量复制，这让我们回到O(n)您对解决方案的第一个猜测。
/* 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 实现，但也许存在一个。
正如书中给出的解释，对于字符串数组中的任何单词，都会创建一个新的句子对象，并且该句子对象首先复制前一个句子，然后遍历到数组的末尾，然后附加新单词，因此复杂度的n^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)。
请注意，在 Java 中附加到字符串 using+=确实表现出本书解释中描述的低效行为，因为它必须分配一个新字符串并将两个字符串中的所有数据复制到其中。所以如果你这样做，它是 O(n^2)：
String sentence = "";
for (String w : words) {
sentence += w;
}
但是 usingStringBuffer不应该产生与上述示例相同的行为。StringBuffer这是首先存在的主要原因之一。
这是我对他们如何得到 O(n^2) 的计算
我们将忽略声明 StringBuffer 的 CPU 时间，因为它不会随最终字符串的大小而变化。
在计算 O 复杂度时，我们关注最坏的情况，当有 1 个字母字符串时会发生这种情况。我将在这个例子之后解释：
假设我们有 4 个单字母字符串：“A”、“B”、“C”、“D”。
读入 A：查找 StringBuffer 结尾的 CPU 时间：0 追加“A”的 CPU 时间：1
读入 B：查找 StringBuffer 结尾的 CPU 时间：1 追加“B”的 CPU 时间：1
读入 C：查找 StringBuffer 结尾的 CPU 时间：2 附加“C”的 CPU 时间：1
读入 D：查找 StringBuffer 结尾的 CPU 时间：3 追加“D”的 CPU 时间：1
最后将 StringBuffer 复制到 String 的 CPU 时间：4
总 CPU 时间 = 1 + 2 + 3 + 4 + 4
如果我们将其推广到 n 个 1 字母单词：
1 + 2 + 3 + ...... + n + n = 0.5n(n+1) + n
我通过使用算术序列和的公式来做到这一点。
O(0.5n^2 + 1.5n) = O(n^2)。
如果我们使用多字母词，我们将不得不更频繁地查找 StringBuffer 的结尾，从而导致 CPU 时间更短和“更好”的情况。