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

Question

这是Cracking the Coding Interview ^第 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为第二等......

然而,她没有提到空间复杂性.我知道面试官喜欢问你解决方案的时间和空间复杂性.这个解决方案的空间复杂性是什么？

我最初的猜测是O(n ²),因为在每个级别n都有n个递归调用.所以你要加n + n - 1 + n - 2 + n - 3 ..... + 1得到^{n(n + 1)}/₂,它在O(n ²)中.我推断有n个递归调用,因为你必须在每个级别回溯n次,并且空间复杂性是你的算法所做的递归调用的次数.例如,当考虑"TOP"的所有排列时,在级别上,3个递归调用,gR([O,P],2,"T"),gR([P,T],2,"O"),制作gR([T,O],2,"P").我对空间复杂性的分析是否正确？

Answer 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 ²)的原因是由于word字符串.当下n降到0时,将len通过调用来占用堆栈条目generateRecurse.len最多会有堆栈条目,因此堆栈的空间使用量只有O(n); 但是每个堆栈条目都有自己的堆栈条目word,它们将同时存在于堆栈中; 并且这些word参数的长度为1,2,...,len当然这相加(len * (len+1)) / 2,这意味着空间使用将是O(n ²).

关于堆栈框架的更多信息:似乎对堆栈框架基础知识的解释会有所帮助......

"堆栈帧"只是内存区域的"堆栈"的一部分.通常,堆栈是预定义的存储区域; 但是,堆栈帧的位置和大小不是预定义的.当程序第一次执行时,堆栈中不会有任何东西(实际上,那里可能会有一些初始数据,但是假设没有什么,只是为了简单起见).所以内存的堆栈区域如下所示:

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,它是否使用相同或不同的参数调用无关紧要.这没关系,因为程序不记得上次使用的参数.它只知道从堆栈指针开始的内存区域是空的并且可以使用.该计划不知道最近在那里生活的框架.那个框架消失了,消失了,消失了.

如果您可以遵循这一点,您可以看到在计算空间复杂性时以及仅查看堆栈使用的空间量时,唯一重要的是,在任何一个时间点堆栈上可以存在多少帧？过去可能存在但不再存在的帧与计算无关,无论调用哪些方法参数.

(PS如果有人计划指出我在这个或那个细节上的技术错误 - 我已经知道这是一个粗略的过度简化.)