了解这个时间复杂性问题(破解编码面试)

Question

问题：

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

所以这个的解决方案是O(xn^2(

据我了解，每次迭代，变量"句子"中的字母数量都会增加 1。我认为哪个将是 O(n^2(？

">

x"只是"单词"数组中的字母数吗？

答：在每次串联时，都会创建字符串的新副本，并逐个字符复制两个字符串。第一次迭代要求我们复制 x 个字符。第二次迭代需要复制 2x 个字符。第三次迭代需要 3 倍，依此类推。因此，总时间为 O(x + 2x + ...x nx(。这简化为 O(xn^2(

Answer 1

答案在两个方面是错误的。 O(xn^2( 不存在。 在大 O 中，您删除所有常量。 如果这是正确的(事实并非如此(，那将是 O(n^2(。

下一部分取决于语言、+ 对字符串的实现和字符串类本身。 如果字符串类是可变的，那么 + 应该是 O(n(，假设它有一个不错的实现(不会导致每次使用 + 时重新定位和复制(。 如果字符串类是不可变的，则取决于 String 的实现方式 - 它是对所有数据使用单个字符缓冲区，还是可以处理有序列表中的多个字符指针？ 当然，即使在最糟糕的实现中，它也不会是 O(n^2(，更像是 O(2n(，它是 O(n((每次迭代 2 个副本(。 任何给我 O(n^2( 答案的人都会被标记为错误。 但实际上，任何现代 String 类实现都是没有常量的 O(n(，并且在空间中几乎是 O(n*l((其中 n 是单词数，l 是平均单词长度(。

class String {
String base;   //used for appended strings
String additional;  //used for appended strings
char baseData[];  //used for pure strings
String(String base, String additional) {
this.base = base;
this.additional = additional;
}
operator + (String newString) {
return new String(this, newString);
}
//As an example of how this works
int length() {
if(base != null) {
return base.length()+additional.length(); //This can be cached, and should be for efficiency.
}
else {
return baseData.length;
}
}
}

请注意，+ 是 O(1(。 是的，我知道Java没有运算符重载，该函数用于显示其实现方式。