Сколько стоит операция + над строкой в ​​Java?

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);

новая строка (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

Из «Эффективной Явы» Джоша Блоха; Пункт 33 в книге:

Для многократного использования оператора конкатенации строк для конкатенации n строк требуется квадратичное время> в n ... Когда две строки объединяются, содержимое обеих копируется.

Использовать StringBuilder. Я считаю, что его производительность O (n).