我的 Count and Say 递归解决方案的 space 复杂度是多少？

Question

给定一个数字序列：1, 11, 21, 1211, 111221, … 序列中数的生成规则如下： 1 是 "one 1" 所以 11。 11 是 "two 1s" 所以 21。 21 是 "one 2 followed by one 1" 所以 1211。找到此序列中的第 n 个数字。假设： n从1开始，第一个数是“1”，第二个数是“11”

我的解决方案：

public String countAndSay(int n) {
List<Integer> result = helper(n);
StringBuilder sb = new StringBuilder();
for(Integer num : result) {
      sb.append(num);
}
return sb.toString();
}

private List<Integer> helper(int n) {
List<Integer> result = new ArrayList<Integer>();
//base case
if (n == 1) {
     result.add(1);
     return result; 
}
List<Integer> smaller = helper(n - 1);
int count = 1;
for (int i = 0; i < smaller.size(); i++) {
    if (i + 1 > smaller.size() - 1 ||
              !smaller.get(i + 1).equals(smaller.get(i))) {
         result.add(count);
         result.add(smaller.get(i));
         count = 1;
    } else {
         count++;
    }
}
    return result;
}

我对大 O 表示法 space 复杂性的理解是，虽然该方法是运行，但不等待垃圾回收的最大可能额外 space。所以我对这个解决方案的 space 复杂性的想法是因为递归调用是由行 "List smaller = helper(n - 1);" 完成的，较低级别递归调用的额外 space 已经在等待垃圾收集.这样low level的时间复杂度就不应该计入当前level。该解决方案的 space 复杂度应该是 O(n)。我说的对吗？

Answer 1

是的，从 java 的角度来看，你是对的。大 O 符号表示 space/time 随着输入大小的增加而增长的顺序。您的代码占用的 space 量将随着 n 输入的增加而线性增加。所以这个解决方案的 space 复杂度确实是 O(n).

对于递归，space 复杂性涉及在最坏情况下 space 进入 recursion/function 堆栈。因为当前在递归堆栈中的函数调用不符合当前垃圾回收调用的条件。当调用 helper(1) 时，此程序将占用的最大值 space 因为此时 helper(n), helper(n - 1) .... helper(2) 所有使用本地资源的调用都在递归堆栈中，不符合垃圾回收条件。

但是，您可以在常量 space 中执行此操作而无需递归。

public String countAndSay(int n) {
        StringBuilder curr = new StringBuilder("1");
        StringBuilder prev;
        int count;
        char say;
        for (int i = 1; i < n; i++) {
            prev = curr;
            curr = new StringBuilder();       
            count = 1;
            say = prev.charAt(0);

            for (int j = 1, len = prev.length(); j < len; j++) {
                if (prev.charAt(j) != say){
                    curr.append(count).append(say);
                    count = 1;
                    say = prev.charAt(j);
                }
                else count++;
            }
            curr.append(count).append(say);
        }                   
        return curr.toString();

}

希望对您有所帮助！

编辑

I still have some confusion about the detail. When we called help(1), all help(2) to help(n) is in recursion stack, yet at that time, the space complexity for each stack is O(1) since we only created an empty List, and the maximum space complexity would be (n-1) * O(1) + O(n)(this is the list of helper(1)) = O(n).What I want to make sure is wheater this analysis is correct.

不是，这是递归栈的图片。您可以设置断点并调试以查看实际情况。

call           result size(when entered)    result size(when function returns)
helper(n)        0                               x(n)
helper(n - 1)    0                               x(n - 1)
helper(n - 2)    0                               x(n - 2)
.......
......
helper(3)        0                               x2
helper(2)        0                               x1
helper(1)        0                               1

此处x(i)是执行此块后的结果大小：

int count = 1;
for (int i = 0; i < smaller.size(); i++) {
    if (i + 1 > smaller.size() - 1 ||
              !smaller.get(i + 1).equals(smaller.get(i))) {
         result.add(count);
         result.add(smaller.get(i));
         count = 1;
    } else {
         count++;
    }
}

您可以使用纸笔或调试来查看递归引擎盖下到底发生了什么。

我的 Count and Say 递归解决方案的 space 复杂度是多少？

What is the space complexity of my recursive solution for Count and Say?

java

algorithm

recursion

space-complexity

编辑