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

摘自 Josh Bloch 的《Effective Java》；书中第33条：

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

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

Answer 2

Java字符串是不可变的.每次你这样做:

S + = C;

你真的在说:

s = new String(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具有明显优势的案例之一.