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

答案在两个方面是错误的。O(xn^2)不存在。在大O中,你去掉所有常数。如果这是正确的(不是),它将是O(n^2)。

下一部分取决于语言、+在字符串上的实现以及字符串类本身。如果string类是可变的,那么+应该是O(n),假设它有一个合适的实现(不会在每次使用+时导致重新定位和复制)。如果string类是不可变的,则取决于字符串的实现方式—它是对所有数据使用单个字符缓冲区,还是可以处理有序列表中的多个字符指针?当然,即使在最差的实现中,也不会是O(n^2),更像O(2n),即O(n)(每次迭代2个副本)。任何回答O(n^2)的人都会被判为错误。但实际上,任何现代的字符串类实现都是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没有操作符重载,函数是用来展示它是如何实现的。