为什么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性能时通常都很草率。这是地方性的。