我知道StringBuffer的append()操作需要O(1)时间，并且与String连接相比，它避免了创建多个String对象的开销。
那么对于insert(int offset, char c)呢？
我需要反复调用此操作，逐个以相反的顺序添加新字符到StringBuffer对象中。例如：
StringBuffer sb = new StringBuffer();
sb.insert(0, 'c');
sb.insert(0, 'b');
sb.insert(0, 'a');
System.out.println(sb.toString()); //prints out "abc";
在理想情况下，如果StringBuffer对象在内部是一个字符链表的话，每个insert(0, c)操作应该是O(1)。我希望确认这是否确实如此。
StringBuffer 的 insert 操作的时间复杂度为 O(n)。 这是因为它必须将多达 n 个字符向上移动，以腾出空间来插入元素。
"bc"
insert(0, 'a') => "_bc" => "abc"
insert方法来解决这个问题。你可以按相反的顺序迭代字母，然后调用O(1)的append方法。
StringBuffer类是AbstractStringBuilder的子类，它定义了一个char[]数组来保存字符。在调用insert方法时，它使用System.arraycopy将现有字符移开。StringBuffer是AbstractStringBuilder的子类的呢？我从这个链接中查看 link，但是没有找到它继承了AbstractStringBuilder。 - ErencieSystem.arraycopy(value, offset, value, offset + 1, count - offset);来进行元素移位。 - Erencie嗯，这是一种实现细节，但我不会期望它是字符的链表。我期望它是一个具有长度的char[]，基本上就像一个字符的ArrayList。因此，在缓冲区的开头插入字符意味着复制所有其他数据。
这一直是我看到的每个实现的基础 - 与更常见的实现相比，字符的链接列表将具有巨大的内存（和分配时间）成本。包含对字符串部分引用 的列表或树结构（请参见"rope"）不会有同样的成本，但我个人没有看到过使用绳子的java.lang.StringBuilder或java.lang.StringBuffer的Java实现。所以，至少几乎总是O(n)。
StringBuilder，append 实际上也不是 O(1) - 在最好的情况下，它是O(N)，其中N为你要添加的数据的大小，在最坏的情况下，当扩展缓冲区时需要创建一个副本。 - Jon Skeet我在文档中找不到它，但很有可能不是O(1),因为 StringBuffer 内部维护了一个 char[] 缓冲区。所以对于一个长度为 n 的序列，这些操作所需的总时间是O(n²)，因为每个 insert(0, c) 都需要将所有当前内容向右移动1个位置。
更有效的方法是只需使用append添加所有字符，并在最后使用sb.reverse()。整体复杂度为 O(n) - 每个append的平均复杂度为O(1)，并且反转操作的复杂度为O(n)。
此外，除非您有多个线程访问您的StringBuffer，否则建议将其替换为StringBuilder。
O(n^2)的操作是如何实现的？难道不应该是O(n)吗？谢谢。 - chris
AbstractStringBuffer；虽然它不是我们从标准的 java.lang 包中使用的 StringBuffer，但我猜测 StringBuffer 的实现大致相似。 - Erencie