我对空间复杂性的分析正确吗？

一尘不染

我对空间复杂性的分析正确吗？

algorithm

这是来自《破解编码面试》第 5 版的问题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”之类的单词，第一个字母有三种可能性，第2个字母有3种可能性。第二，依此类推…

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

我最初的猜测是O（n 2），因为在每个级别n上都有n个递归调用。因此，您可以将n + n-1 + n-2 + n-3 ..... + 1加上n （n +
1） ⁄ 2，它在O（n 2）中。我认为存在n个递归调用，因为您必须在每个级别上回溯n次，并且空间复杂度是算法进行的递归调用的数量。例如，当考虑“
TOP”的所有排列时，在级别上进行3次递归调用gR（[O，P]，2，“ T”），gR（[P，T]，2，“ O”），制成gR（[T，O]，2，“
P”）。我对空间复杂性的分析正确吗？

阅读 255

2020-07-28

共1个答案

一尘不染

我认为您得到了正确的答案，但原因有误。递归调用的数量与它无关。当您进行递归调用时，它将为堆栈增加一定数量的空间。但是当该调用退出时，将释放堆栈空间。因此，假设您有以下内容：

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

method(1);

尽管method自己调用了10000次，但method在任何时候，堆栈上最多只能进行2次调用。因此，空间复杂度将为O（1）[常数]。

您的算法具有空间复杂度O（n
2）的原因是由于word字符串。当n降至0时，将len调用调用栈堆栈generateRecurse。len最多会有堆栈条目，因此堆栈的空间使用量仅为O（n）；但是每个堆栈条目都有自己的word，它们将同时存在于堆中；并且这些word参数的长度为1，2，…，，len它们
的确合计为(len * (len+1)) / 2，这意味着空间使用量为O（n 2）。

关于堆栈帧的更多信息： 似乎对堆栈帧的基础进行解释会有所帮助…

“堆栈框架”只是“堆栈”一部分的内存区域。通常，堆栈是内存的预定义区域。但是，堆栈帧的位置和大小尚未预定义。第一次执行程序时，堆栈上没有任何内容（实际上，那里可能会有一些初始数据，但是可以说没有什么，只是为了保持简单）。因此，内存的堆栈区域如下所示：

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将返回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返回。之后method2的回报，它的参数和局部变量将无法再访问。因此，可以丢弃整个框架。这可以通过将堆栈指针移回之前的位置来完成。（“上一个堆栈指针”是保存在某一帧中的内容之一。）堆栈返回如下所示：

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

这意味着在这一点上，机器将以堆栈指针开头的堆栈部分视为“未使用”。说method2重用框架并不太正确。您不能真正使用已经不存在的东西，而其method2框架不再存在。从概念上讲，所有堆栈都具有很大的空白区域。如果method1调用另一个方法，无论是method2，method1递归System.out.println还是其他方法，都将在堆栈指针现在指向的位置创建一个新框架。该框架的大小可以比以前的method2框架小，相等或更大。它将占用method2框架所在的部分或全部内存。如果是另一个电话method2，无论使用相同还是不同的参数调用都无关紧要。没关系，因为程序不会记住上次使用的参数。它所知道的只是从堆栈指针开始的内存区域为空，可以使用。该程序不知道最近在那里住过什么框架。那帧不见了，不见了，不见了。

如果您可以遵循此方法，则可以看到，在计算空间复杂度并仅查看堆栈使用的空间量时，唯一重要的是，在任一时间点堆栈上可以存在多少帧？过去使用过的帧不再使用，与计算无关，无论使用何种参数调用方法。

（附言：如果有人打算指出我在技术上对这个或那个细节有何错误，我已经知道这是一个过分的简化。）

2020-07-28