Som*_*one 31 java complexity-theory big-o stringbuffer time-complexity
我正在从我的电子书中粘贴这个文本.它说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)运行时间.哎哟!
有人可以更清楚地解释这个答案吗？
小智 23
这似乎是一个误导的问题,因为我刚刚读了那本书.书中的这部分内容是拼写错误!以下是上下文:
================================================== =================
问题:此代码的运行时间是多少？
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)可以帮助你避免这个问题'.
por*_*ges 17
接受的答案是错的.StringBuffer已摊销O(1)追加,因此n追加将为O(n).
如果它不是O(1)追加,StringBuffer则没有理由存在,因为用普通String连接编写该循环也是O(n ^ 2)!
Bri*_*n L 17
当它以高级别编写时,回答有关此代码复杂性的问题有点困难,这会抽象出实现的细节.在Java文档似乎并没有给予任何保证在中的复杂性方面append的功能.正如其他人所指出的那样,StringBuffer可以(并且应该)编写类,以便附加字符串的复杂性不依赖于保持的字符串的当前长度StringBuffer.
但是,我怀疑这个问这个问题的人只是简单地说"你的书是错的!". - 相反,让我们看看正在做出的假设,并明确作者试图说的是什么.
您可以做出以下假设:
new StringBuffer是O(1)w在words为O(1)sentence.toString最多为O(n).问题实际上是什么顺序sentence.append(w),这取决于它是如何在内部发生的StringBuffer.天真的方式是像Shlemiel the Painter那样做.
假设您使用C样式的以null结尾的字符串作为内容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).
Nik*_*zov 12
我尝试使用这个程序检查它
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
小智 12
我认为书中的这些文字必须是拼写错误,我认为正确的内容如下,我修复它:
================================================== =================
问题:此代码的运行时间是多少？
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逐个字符地复制字符串，那么上面的算法是
\xce\x98(n*m)，或者O(n*m)，其中n是字数，m是平均字长，并且你的书是错误的。我假设您正在寻找严格的界限。
本书的答案不正确的简单示例：\nString[] words = [\'alphabet\']根据本书的定义，n=8，因此算法将受到 64 个步骤的限制。是这样吗？显然不严格。我看到 1 个赋值操作和 1 个包含 n 个字符的复制操作，因此您大约需要 9 个步骤。正如我上面所说明的，这种行为是由 的界限预测的O(n*m)。
我做了一些挖掘，这显然不是一个简单的角色复制。看起来内存正在被批量复制，这让我们回到了O(n)您对解决方案的第一个猜测。
/* StringBuffer is just a proxy */\npublic AbstractStringBuilder append(String str) \n{\n if (str == null) str = "null";\n int len = str.length();\n ensureCapacityInternal(count + len);\n str.getChars(0, len, value, count);\n count += len;\n return this;\n}\n\n/* java.lang.String */\nvoid getChars(char dst[], int dstBegin) {\n System.arraycopy(value, offset, dst, dstBegin, count);\n}\n你的书要么很旧，要么很糟糕，或者两者兼而有之。我没有足够的决心去挖掘 JDK 版本来找到 StringBuffer 的不太优化的实现，但也许存在一个。
\n