计算字符串压缩的空间复杂度 - 破解编码访谈

Question

我试图了解下面一段代码的空间复杂性。代码将字符串从“aabbbb”压缩为“a2b4”。问题是破解编码面试第5版（2013年）的问题5，第1章，代码取自solutions

 public static String compressBetter(String str) {
    int size = countCompression(str);
    if (size >= str.length()) {
        return str;
    }
    StringBuffer mystr = new StringBuffer();
    char last = str.charAt(0);
    int count = 1;
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) == last) {
            count++;
        } else {
            mystr.append(last);
            mystr.append(count);
            last = str.charAt(i);
            count = 1;
        }
    }
    mystr.append(last);
    mystr.append(count);
    return mystr.toString();
}   

哪里

public static int countCompression(String str) {
    if (str == null || str.isEmpty()) return 0;
    char last = str.charAt(0);
    int size = 0;
    int count = 1;
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) == last) {
            count++;
        } else {
            last = str.charAt(i);
            size += 1 + String.valueOf(count).length();
            count = 1;
        } 
    }
    size += 1 + String.valueOf(count).length();
    return size;
}

根据作者compressBetter有O（N）空间复杂性。为什么不是O（1）？在countCompression的每次运行中，我们持有last，size和count以及类似的compressBetter（持有countCompression变量加上mystr，last，count。我对空间复杂性的理解是“算法在任何时候需要/保持多少内存”。单词空间复杂性不同于时间复杂性不是累积的

请注意，作者在书中仅考虑人们所称的“辅助空间复杂性”（没有存储输入所需的空间），如上例所示。此外，afaik在这本书的errata没有条目。

更新：我的混淆来自以下示例（同一本书中的问题1.1）

public static boolean isUniqueChars2(String str) {
  boolean[] char_set = new boolean[256];
  for (int i = 0; i < str.length(); i++) {
    int val = str.charAt(i);
    if (char_set[val]) return false;
    char_set[val] = true;
  }
  return true;
}    

尽管有256个布尔数组分配，但这是O（1） - 我认为分配在计算空间复杂度时无关紧要。但实际上它是O（1）因为所需的空间是恒定的并且与输入大小无关（与mystr Stringbuffer不同）。

Answer 1

只需将我之前的评论转换为答案：您持有的StringBuffer可能具有与String的大小成比例的大小。试想一下你有一个没有连续重复字符的输入字符串的情况（最糟糕的情况）。

Answer 2

你问的是compressBetter的空间复杂性，其中包括对countCompression的调用，但也执行额外的工作。

虽然countCompression的空间复杂度确实是O(1)，但compressBetter在最坏的情况下（其中没有输入O(N)的两个连续字符相等）具有线性空间复杂度（即String），因为在这种情况下它产生2N个字符的StringBuffer。