algorithm - 字符串构建算法的时间复杂度

Question

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

这本书报告这是 O(xn^2)

这是我的作品:

1 调用最初创建String sentence

有N次调用(由于for循环有N次调用)

然后有N次调用赋值sentence = sentence + w

最后调用发送return sentence;

总计:

这给出 O(N^2 + 2) = O(N^2)

问题(1) 我的操作正确吗？

(2) 他们从哪里得到 O(xn^2) 中的额外因子 x？

谢谢!

Answer 1

这是一个写得不好的例子，因为它会重新分配句子 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

如果 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)。 ..