为什么StringBuilder.append时间复杂度是O(1)

Question

通过摊销分析，我们知道使用

N

方法进行

StringBuilder#append

插入需要

O(N)

时间。但这就是我迷路的地方。考虑一下，其中

inputString

是来自用户的输入字符串。

for (int i = 0; i < N; i++) {
   s.append(inputString); 
   // where s is an empty StringBuilder object at the beginning 
   // and inputString is the string that is taken from the user
}

时间复杂度是否应该为

O(inputString.length * N)

，因为

append()

将输入字符串复制到

StringBuilder

N

次的末尾？为什么我们认为

append()

需要

O(1)

时间复杂度，而它应该被视为

O(inputString.length)

？

几乎在我检查的所有地方，它都被认为是

O(1)

，例如 https://quora.com/What-is-the-complexity-of-Java-StringBuffer-append 以及 的复杂度是多少就这么简单的一段代码？

Answer 1

由于append()将输入字符串复制到StringBuilder的末尾N次，时间复杂度是否应该为O(inputString.length * N)？

是的。

为什么我们认为append()需要O(1)时间复杂度，而它应该被认为是O(inputString.length)？

追加单个字符时是O(1)。 StringBuilder 就像 ArrayList。当您附加单个项目时，成本为 O(1)。追加字符串就像调用 addAll() - 成本与字符串的长度/添加的项目数成正比。

看来你对一切的理解都是正确的。问题是人们在讨论 Big-O 性能时常常很草率。这是地方病。

Answer 2

这取决于您在 O(*) 表达式中计算的内容。如果它是“将字符复制到缓冲区数组中的次数”，那么它必须是 O(inputString.length * N)，因为生成的缓冲区将包含那么多字符。然而，在实践中，主导运行时间的是“分配新 byte[] 的次数”，因为您需要更大的缓冲区。如果这就是您所计算的，那么追加的时间复杂度将摊销为 O(1)，代价是（可能）分配比结果字符串所需的空间更多的空间。实现几乎与 ArrayList#add 相同，也是“摊销”O(1)。这最终是字符串连接和 StringBuffer#append 之间的区别。尝试此代码以获得更深入的了解

    StringBuilder buffer = new StringBuilder();
    for (int i = 0; i < 10_000; i++) {
        buffer.append(<<some string value>>);
        System.out.println(buffer.capacity());
    }