这段简单代码的复杂性是什么？

time-complexity java big-o complexity-theory stringbuffer

2022-09-01 07:10:42

我正在从我拥有的电子书中粘贴此文本。它说了O（n²）的复杂性，并给出了解释，但我不明白如何。

问：此代码的运行时间是多少？

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

书中给出的答案是：

O（n²），其中 n 是句子中的字母数。原因如下：每次将字符串附加到句子时，您都会创建句子的副本并遍历句子中的所有字母以复制它们如果每次在循环中必须迭代最多n个字符，并且您至少循环了n次，这将为您提供O（n²）运行时间。哎哟！

有人可以更清楚地解释这个答案吗？

答案 1

这似乎是一个误导的问题，因为我刚才碰巧读了那本书。书中的这部分文字是错别字！以下是上下文：

===================================================================

问：此代码的运行时间是多少？

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²），其中 n 是句子中的字母数。原因如下：每次将字符串附加到句子时，您都会创建句子的副本，并遍历句子中的所有字母以复制它们。如果每次都必须在循环中循环访问最多 n 个字符，并且至少循环 n 次，则会得到 O（n²）个运行时间。哎哟！使用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²）解决方案（第一个）与“优化”的解决方案（后者）完全相同。因此，我的结论是，作者试图呈现其他内容，例如在追加每个下一个字符串时始终将旧句子复制到新缓冲区，作为O（n²）算法的示例。StringBuffer不应该那么愚蠢，因为作者还提到“使用StringBuffer（或StringBuilder）可以帮助你避免这个问题”。

答案 2

当在高级级别编写此代码时，很难回答有关此代码的复杂性的问题，该代码抽象出实现的细节。Java文档似乎没有在函数的复杂性方面给出任何保证。正如其他人所指出的，可以（并且应该）编写类，以便追加字符串的复杂性不依赖于中保存的字符串的当前长度。appendStringBufferStringBuffer

然而，我怀疑对提出这个问题的人来说，简单地说“你的书是错的！”并不是那么有帮助 - 相反，让我们看看正在做出什么假设，并弄清楚作者想说什么。

您可以做出以下假设：

创建一个是 O（1）new StringBuffer
获取下一个字符串是 O（1）wwords
返回最多为 O（n）。sentence.toString

问题实际上是的顺序是什么，这取决于它如何在内部发生。天真的方法是像画家施勒米尔一样做到这一点。sentence.append(w)StringBuffer

愚蠢的方式

假设您对的内容使用 C 样式的空终止字符串。找到此类字符串结尾的方法是逐个读取每个字符，直到找到空字符 - 然后要追加新字符串S，您可以开始将字符从S复制到字符串（以另一个空字符结尾）。如果以这种方式书写，则为 O（a + b），其中 a 是当前在中的字符数，b 是新单词中的字符数。如果循环访问一个单词数组，并且每次都必须在追加新单词之前读取刚刚附加的所有字符，则循环的复杂度为 O（n^2），其中 n 是所有单词中的字符总数（也是最后一句中的字符数）。StringBufferStringBufferappendStringBuffer

更好的方法

另一方面，假设的内容仍然是一个字符数组，但我们也存储一个整数，它告诉我们字符串的长度（字符数）。现在我们不再需要读取中的每个字符才能找到字符串的末尾;我们可以在数组中查找索引，数组是 O（1）而不是 O（a）。然后，该函数现在仅依赖于要追加的字符数 O（b）。在这种情况下，循环的复杂度为 O（n），其中 n 是所有单词中的字符总数。StringBuffersizeStringBuffersizeappend

...我们还没有完成！

最后，实现还有一个方面尚未涉及，那就是教科书中的答案实际提出的一个方面 - 内存分配。每次你想写更多的字符到你的，你不能保证你的字符数组中有足够的空间来实际容纳新单词。如果没有足够的空间，您的计算机需要首先在干净的内存部分分配更多的空间，然后复制旧阵列中的所有信息，然后它可以像以前一样继续。像这样复制数据将花费O（a）时间（其中a是要复制的字符数）。StringBufferStringBuffer

在最坏的情况下，每次添加新单词时都必须分配更多内存。这基本上把我们带回了循环具有O（n^2）复杂性的原点，并且正是本书所暗示的。如果你假设没有发生任何疯狂的事情（单词不会以指数速度变长！），那么你可以通过让分配的内存呈指数级增长，将内存分配的数量减少到更像O（log（n））的东西。如果这是内存分配的数量，并且通常的内存分配是O（a），那么仅归因于循环中内存管理的总复杂性为O（n log（n））。由于追加工作是 O（n）并且小于内存管理的复杂性，因此函数的总复杂度为 O（n log（n））。

同样，Java文档在容量增长方面并没有帮助我们，它只是说“如果内部缓冲区溢出，它会自动变大”。根据它是如何发生的，你最终可能会得到O（n^2）或O（n log（n））。总体而言。StringBuffer

作为留给读者的练习：通过消除内存重新分配问题，找到一种简单的方法来修改函数，使整体复杂性为O（n）。