Временная сложность алгоритма строки сборки

Question

String joinWords (String[] words){ 
    String sentence = ""; 
    for(String w: words){ 
    sentence = sentence + w; 
    } 
    return sentence; 
} 

В книге отчетов, чтобы это было O(xn^2)

Вот мой рабочий:

1 вызов для создания String sentence первоначально

Есть N звонки (из-за N вызывает цикл for)

затем есть N вызовов для назначения sentence = sentence + w

Последний звонок отправить return sentence;

Итого:

Что дает O (N^2 + 2) = O (N^2)

Вопросы (1) Является ли мой правильная работа?

(2) Где он получает дополнительный коэффициент x в O(xn^2)?

Спасибо!

Answer 1

Итого:

Что дает O (N^2 + 2) = O (N^2)

Поместите свой цикл, как это:

String joinWords (String[] words){ 
    String sentence = ""; 
    // words.length is a constant, no calls are made 
    for(int i=0; i<words.length; i++){ 
    sentence = sentence + w; 
    } 
    return sentence; 
} 

В то время как sentence = sentence + w; действительно «манипулирует данными», откуда берется ваш другой N в предполагаемом O (N^2)?

Answer 2

, что плохо написана пример, потому что он будет перераспределять предложение N раз вместо того, чтобы один раз вызывая O(x.N^2)

String sentence = ""; 
for(String w: words) // this loops N times (if N is number of words) 
sentence = sentence + w; // this reallocates the whole thing 

If sentence = sentence + w; будет O(1) тогда результат будет O(N), но это не так, потому что:

sentence = sentence + w; 

в реальности что-то вроде этого:

String temp = new string of size (sentence.size + w.size); 
for (i=0;i<sentence.size;i++) temp[i]=sentence[i]; 
for (i=0;i<w.size;i++) temp[i+sentence.size]=w[i]; 
sentence=temp; // just pointer assignment O(1) 
delete temp; 

O(M) Что где M является количество букв в результате предложение, которое является x.N в среднем (x среднее число букв в слове).

Таким образом, окончательный сложность O(x.N^2) (не с учетом амортизации), а это может быть просто O(x.N) если бы использовать шаг предраспределения ...