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

Question

通过摊销分析，我们知道使用 StringBuilder#append 方法的 N 插入需要 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 as well as What is the complexity of this simple piece of code?

Answer 1

Should this have time complexity of O(inputString.length * N) since append() copies the input string to the end of the StringBuilder N times?

是的。

Why do we consider that append() takes O(1) time complexity whereas it should be considered as O(inputString.length)?

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

看来您理解正确。问题是人们在讨论 Big-O 性能时往往草率。这是地方病。

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

Why StringBuilder.append time complexity is O(1)

java

stringbuilder