计算 space 字符串压缩的复杂度 - 破解编码面试

Question

我试图理解 space 以下代码的复杂性。该代码将字符串从 "aabbbb" 压缩到 "a2b4"。问题是 Cracking the coding interview version 5 (2013) 第 1 章的问题 5，代码取自 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) space。 为什么不是 O(1)？在 countCompression 的每个运行中，我们持有 last、size 和 count 以及类似的 compressBetter（持有 countCompression 变量加上mystr, last, count。我对space复杂度的理解是"how much memory the algorithm needs/holds at any time"。换句话说，space复杂度不像时间复杂度那样是不累积的。

请注意，作者在书中只考虑了人们称为 "auxiliary space complexity" 的内容（没有存储输入所需的 space），如上例所示。另外，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) - 我认为分配在计算 space 复杂度时无关紧要。但实际上它是 O(1)，因为所需的 space 是常数并且与输入大小无关（与 mystr Stringbuffer 不同）。

Answer 1

您问的是 compressBetter 的 space 复杂度，其中包括对 countCompression 的调用，但还执行额外的工作。

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

Answer 2

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

计算 space 字符串压缩的复杂度 - 破解编码面试

Calculating space complexity of string compression - Cracking the coding interview

java

string

complexity-theory

space-complexity