java - 在 Java 中对 String 进行 + 操作的成本是多少？

Question

对于这个 for 循环，运行时间是 O(n) 还是 O(n^2)：

char[] ar = new char[1000];
String s = "";
Arrays.fill(ar, 'a');
for(Character c: ar){
    s += c;
}

所以基本上，字符串上 + 的运行时间是多少？它在 Java 中是如何在幕后工作的？

Answer 1

Java 字符串是不可变的。每次你这样做：

s+=c;

你真的是在说：

s = 新字符串(s + c);

new String(s + c) 必须分配一个长度为 s + 1 的字符串，或者：

1 2 3 4 5 6 7 8 9 ... 等等。

由于 Sum(1..N) == (n + 1) (n / 2)，所以这是 O(n^2)。

StringBuilder 具有明显优势的情况之一。

Answer 2

摘自 Josh Bloch 的“Effective Java”；书中第33条：

重复使用字符串连接运算符连接n个字符串需要时间二次> in n...当连接两个字符串时，复制两者的内容。

使用字符串生成器。我相信它的性能是 O(n)。