这段简单代码的复杂性是什么？
我正在从我的电子书中粘贴这个文本。 它说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不应该太傻，因为作者还提到’With StringBuffer（或StringBuilder）可以帮助你避免这个问题’。
当它以高级别编写时，回答有关此代码复杂性的问题有点困难，这会抽象出实现的细节。 Java文档似乎没有在append函数的复杂性方面提供任何保证。 正如其他人所指出的那样，可以（并且应该）编写StringBuffer类，以便附加字符串的复杂性不依赖于StringBuffer保存的字符串的当前长度。
但是，我怀疑那个问这个问题的人只是简单地说“你的书错了！”。 – 相反，让我们看看正在做出的假设，并明确作者试图说的内容。
您可以做出以下假设：
- 创建一个
new StringBuffer是O（1） - 用
words获取下一个字符串w是O（1） - 返回
sentence.toString.toString最多为O（n）。
问题实际上是sentence.append(w)的顺序是什么，这取决于它在StringBuffer发生方式。 天真的方式是像Shlemiel the Painter那样做。
愚蠢的方式
假设您对StringBuffer的内容使用C样式的以null结尾的字符串。 找到这样一个字符串结尾的方法是逐个读取每个字符，直到找到空字符 – 然后附加一个新字符串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 Test 200000 - 128 ms
java Test 500000 - 370 ms
java Test 1000000 - 698 ms
版本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(); }
================================================== ===================
我对吗？
这实际上取决于StringBuffer的实现。 假设.append()是恒定时间，很明显你有一个O(n)算法，其中n = length of the words array 。 如果.append 不是常量时间，则需要按方法的时间复杂度将O（n）加倍。 如果StringBuffer的当前实现确实逐个字符地复制字符串，则上面的算法是
Θ(n*m)或O(n*m) ，其中n是单词数， m是平均单词长度，你的书是错误的。 我假设你正在寻找一个严格的约束。
书的答案不正确的简单例子： String[] words = ['alphabet']根据书的定义， n=8 ，因此算法将以64步为界。 是这样的吗？ 显然不严格。 我看到1个赋值和1个n个字符的复制操作，所以你得到大约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实现，但也许存在一个。
这本书中有一个拼写错误。
第一例 ：
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级联的摊销复杂性）
正如书中给出的解释，对于字符串数组中的任何单词，都会创建一个新的句子对象，并且该句子对象首先复制前一个句子，然后遍历到数组的末尾，然后附加新单词，因此复杂n^2 。
- 首先将’n’复制到新对象中
- 第二个’n’遍历该数组，然后追加它
因此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中，会出现本书解释中描述的低效行为，因为它必须分配新字符串并将两个字符串中的所有数据复制到其中。 所以，如果你这样做，它是O（n ^ 2）：
String sentence = ""; for (String w : words) { sentence += w; }
但是使用StringBuffer不应该生成与上例中相同的行为。 这是StringBuffer首先存在的主要原因之一。
这是我对他们如何获得O（n ^ 2）的计算
我们将忽略声明StringBuffer的CPU时间，因为它不会随着最终字符串的大小而变化。
在计算O复杂度时，我们关注最坏的情况，当有1个字母的字符串时会发生这种情况。 我将在这个例子后解释：
假设我们有4个单字母字符串：’A’，’B’，’C’，’D’。
读入A：CPU时间查找StringBuffer的结尾：0 CPU时间追加’A’：1
读入B：查找StringBuffer结束的CPU时间：1个CPU时间追加’B’：1
读入C：CPU时间以查找StringBuffer的结尾：2个CPU时间来追加’C’：1
读入D：CPU时间以查找StringBuffer的结尾：3个CPU时间来追加’D’：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时间和更好的情况。