java - 获取算法的运行时间

Question

我在破解编码面试一书中遇到了这个问题(第201页)，但它的解决方案没有足够的意义。于是我们就有了如下的字符串压缩算法:

String compressBad(String str)
{ 
  String compressedString = "";
  int countConsecutive = 0;
  for (int i = 0; i< str.length(); i++)
  {
    countConsecutive++;

    if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1))
    {
      compressedString += "" + str.charAt(i) +  countConsecutive;
      countConsecutive = 0;
    }
  }
    return compressedString.length() < str.length() ? compressedString : str;
}

该算法的运行时间据称为 O(p + k²)(p 是字符串大小，k 是字符序列数)。为什么它有“+k²”？

Answer 1

字符串的运算符 + 和 += 是通过分配新的内存块，然后将两个字符串复制到该新 block 来实现的。

例如类似

String s3 = s1 + s2; // s1, s2 are Strings

通过分配 s1 大小 + s2 大小的新内存，然后将 s1 复制到其中来实现，然后是s2。

就复杂性而言，这与字符串的大小呈线性关系。

正如您所看到的，这可能是浪费且缓慢的，因此在连接多个字符串时(例如在循环中)通常应该避免它。