我对 space 复杂性的分析是否正确？

Question

这是 Cracking the Coding Interview 5^th edition

中的第 9.5 题

问题：编写一个方法来计算字符串的所有排列

这是我的解决方案，编码为 Java（测试它，有效 :)）

public static void generatePerm(String s) {
    Queue<Character> poss = new LinkedList<Character>();
    int len = s.length();
    for(int count=0;count<len;count++)
        poss.add(s.charAt(count));
    generateRecurse(poss, len, "");
}
private static void generateRecurse(Queue<Character> possibles, int n, String word) {
    if(n==0)
        System.out.println(word);
    else {
        for(int count=0;count<n;count++) {
            char first = possibles.remove();
            generateRecurse(possibles, n-1, word+first);
            possibles.add(first);
        }
    }
}

我同意作者的观点，我的解决方案在 O(n!) 时间复杂度内运行，因为要解决这个问题，你必须考虑阶乘，比如像 "top"，第一个字母有3种可能，第二个有2种，以此类推....

但是她没有提到 space 复杂性。我知道面试官喜欢问你解决方案的时间和 space 复杂性。这个解决方案的 space 复杂度是多少？

我最初的猜测是 O(n²) 因为有 n 个递归调用在每个级别 n。所以你会添加 n + n - 1 + n - 2 + n - 3.....+ 1 得到 ⁿ⁽ⁿ⁺¹⁾⁄₂ 在 O(n²) 中。我推断有 n 次递归调用，因为您必须在每个级别回溯 n 次，并且 space 复杂度是您的算法进行的递归调用次数。例如，当考虑 "TOP" 的所有排列时，在 level，3 次递归调用，gR([O,P],2,"T"), gR([P,T],2,"O"), gR([T,O],2,"P")。我对 space 复杂性的分析是否正确？

Answer 1

我认为您的答案是正确的，但原因是错误的。递归调用的次数与它没有任何关系。当你进行递归调用时，它会向堆栈添加一定数量的space；但是当该调用退出时，堆栈 space 被释放。所以假设你有这样的东西：

void method(int n) {
    if (n == 1) {
        for (int i = 0; i < 10000; i++) {
            method(0);
        }
    }
}

method(1);

虽然method调用了自己10000次，但栈上任何一次对method的调用仍然不会超过2次。所以 space 复杂度为 O(1) [常量]。

你的算法具有 space 复杂度 O(n²) 的原因是因为 word 字符串。当 n 降至 0 时，将有 len 个堆栈条目被 generateRecurse 的调用占用。最多会有 len 个堆栈条目，因此堆栈的 space 使用率只会是 O(n)；但是每个堆栈条目都有自己的word，它们将同时存在于堆上； word 参数的长度是 1, 2, ..., len，当然 do 加起来就是 (len * (len+1)) / 2，意味着 space 用法将是 O(n²).

关于栈帧的更多信息： 似乎解释栈帧的基础知识会有所帮助...

A "stack frame" 只是 "stack" 的一部分内存区域。通常，堆栈是预定义的内存区域；然而，栈帧的位置和大小不是预定义的。当一个程序第一次执行时，堆栈上不会有任何东西（实际上，那里可能会有一些初始数据，但为了简单起见，假设什么都没有）。所以内存的栈区看起来是这样的：

bottom of stack                                       top of stack
------------------------------------------------------------------
|                      nothing                                   |
------------------------------------------------------------------
^
+--- stack pointer

（这里假设栈是向上增长的，从低地址到高地址。很多机器都有向下增长的栈。为了简化，我继续假设这是一台栈向上增长的机器。）

当一个方法（函数、过程、子程序等）被调用时，堆栈的某个区域被分配。该区域足以容纳方法的局部变量（或对它们的引用）、参数（或对它们的引用）、一些数据，以便程序在您 return 时知道返回到哪里，以及可能的其他信息- - 其他信息高度依赖于机器、编程语言和编译器。在 Java 中，第一个方法将是 main

bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame |                  nothing                        |
------------------------------------------------------------------
                ^
                +--- stack pointer

请注意，堆栈指针已向上移动。现在 main 呼叫 method1。由于 method1 将 return 变为 main，因此必须保留 main 的局部变量和参数，以便 main 恢复执行。在堆栈上分配了一个具有一定大小的新帧：

bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame | method1's frame |      nothing                  |
------------------------------------------------------------------
                                  ^
                                  +--- stack pointer

然后 method1 调用 method2:

bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame | method1's frame | method2's frame |   nothing   |
------------------------------------------------------------------
                                                    ^
                                                    +--- stack pointer

现在 method2 returns。 method2 returns 后，其参数和局部变量将不再可访问。因此，可以将整个框架抛出。这是通过将堆栈指针移回之前的位置来完成的。（"previous stack pointer" 是保存在某个帧中的内容之一。）堆栈返回看起来像这样：

bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame | method1's frame |        nothing                |
------------------------------------------------------------------
                                  ^
                                  +--- stack pointer

这意味着，在这一点上，机器将看到以堆栈指针开始的堆栈部分为 "unused"。说 method2 的框架被重用是不正确的。你不能真正使用已经不复存在的东西，method2的框架已经不存在了。从概念上讲，堆栈中只有一个很大的空白区域。如果method1调用了另外一个方法，无论是method2，method1递归，System.out.println，还是别的什么，都会在栈指针现在所在的地方创建一个新的frame指向。该框架的大小可以小于、等于或大于以前的 method2 框架。它将占用 method2 帧所在的部分或全部内存。如果是对 method2 的另一次调用，使用相同或不同的参数调用并不重要。没关系，因为程序不记得上次使用了哪些参数。它只知道以堆栈指针开始的内存区域是空的并且可以使用。该程序不知道最近住在那里的是什么框架。那个框架不见了，不见了，不见了。

如果你能做到这一点，你会发现在计算 space 复杂度时以及仅查看堆栈使用的 space 数量时，唯一重要的是，如何在任何一个时间点，堆栈中可以存在许多帧？过去可能存在但不再存在的帧与计算无关，无论使用什么参数调用方法。

(P.S。万一有人想指出我在这个或那个细节上的技术错误——我已经知道这是一个严重的过度简化。)

我对 space 复杂性的分析是否正确？

Is my analysis of space complexity correct?

java

algorithm

recursion

time-complexity

space-complexity