Эффективность конкатенации строк JavaScript

Question

Я занимался практической проблемой, которая заключалась в объединении строк в цикле for.Я видел информацию по старым связанным вопросам на этом сайте, но я хотел знать некоторые другие детали.Книга, из которой я получил практическую задачу (Cracking the Coding Interview), делала решения на Java.Вот упрощенная версия кода, чтобы понять суть:

for(int i = 0; i < str.length; i++){
   string += str.charAt(i) + i;
}

В книге указано, насколько это медленно, потому что конкатенация строк в Java работает в O (n ^ 2).И решением этой проблемы было использование класса StringBuilder в Java.

Однако как это будет работать в Javascript?Работает ли конкатенация строк с использованием "+ =" также в O (n ^ 2) раз?

Answer 1

Для пояснения давайте разберем сложность времени выполнения между конкатенацией String и циклом for.Конкатенация строк в Java - это O (n), потому что Java создает всю новую строку.Поскольку вы поместили его в цикл for, теперь мы умножим еще один n , чтобы получить O (n ^ 2).

Конкатенация строк - это не O (n ^ 2), конкатенация внутри цикла for - это O (n ^ 2).

В JavaScript работает конкатенация строкиными словами, и, что еще более усложняет ситуацию, основа зависит от браузера. Вот статья 2010 года , в которой объясняются некоторые различия.Многие браузеры также оптимизируют для строковых операций.Проверьте этот связанный вопрос о конкатенации строк.