这是从破解编码面试5问题9.5 日版

This is problem 9.5 from Cracking the Coding Interview 5th edition

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

The Problem: Write a method to compute all permutations of a string

下面是我的解决方案，codeD中的Java（测试它，它的工作原理:)）

Here is my solution, coded in Java(test it, it works :) )

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！）的时间复杂度，因为要解决这个问题，你要考虑阶乘，像类似顶字，也有作者三种可能性的第一个字母，2为第二个等等....

I agreed with the author that my solution runs in O(n!) time complexity because to solve this problem, you have to consider factorials, like for a word like "top", there are three possibilities for the first letter, 2 for the second and so on....

然而，她没有做任何提及空间复杂度。我知道，面试官喜欢问你你的解决方案的时间和空间复杂度。什么这个解决方案的空间复杂度是什么？

However she didn't make any mention of space complexity. I know that interviewers love to ask you the time and space complexity of your solution. What would the space complexity of this solution be?

我最初的猜测是为O（n 2 ），因为有n每级n递归调用。所以，你会增加N + N - 1 + N - 2 + N - 3 ..... + 1得到 N（N + 1）＆frasl; 2 这是为O（n 2 ）。我的理由是，有n个递归调用，因为你必须原路返回n将在每个级别的时间和空间复杂度的递归调用你的算法，使数量。例如，考虑到TOP的所有排列，在级别，3递归调用，GR时（[O，P]，2，T），GR（[P，T]，2，O）， Gr（[T，O]，2，P）制成。难道我的空间复杂度的分析是否正确？

My initial guess was O(n2) because there are n recursive calls at each level n. So you would add n + n - 1 + n - 2 + n - 3.....+ 1 to get n(n+1)⁄2 which is in O(n2). I reasoned that there are n recursive calls, because you have to backtrack n times at each level and that space complexity is the number of recursive calls your algorithm makes. For example, when considering all the permutations of "TOP", at level, 3 recursive calls, gR([O,P],2,"T"), gR([P,T],2,"O"), gR([T,O],2,"P") are made. Is my analysis of space complexity correct?

推荐答案

我觉得你得到了正确的答案，但错误的理由。的递归调用的次数没有什么关系吧。当你做一个递归调用，它会添加一定量的空间堆栈;但是，当该调用退出时，堆栈空间被释放。因此，假设你有这样的事情：

I think you got the right answer but for the wrong reason. The number of recursive calls doesn't have anything to do with it. When you make a recursive call, it will add a certain amount of space to the stack; but when that call exits, the stack space is released. So suppose you have something like this:

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

method(1);

尽管方法自称是10000次，仍然会有堆栈上不超过2调用方法的在任何一个时间。因此，空间复杂度是O（1）[常量]。

Although method calls itself 10000 times, there will still be no more than 2 invocations of method on the stack at any one time. So the space complexity would be O(1) [constant].

你的算法的原因有空间复杂度为O（n 2 ）是因为字字符串。当 N 下到0，将有 len个栈条目被拉紧 generateRecurse 。将有 len个最多堆栈条目，所以堆栈空间的使用只会为O（n）;但其中每个堆栈条目都有自己的字，这将堆在同一时间都存在;和那些字参数为1，2，...， len个的长度，这当然的不要的加起来（LEN *（LEN + 1））/ 2 ，这意味着空间的使用将是为O（n 2 ）

The reason your algorithm has space complexity O(n2) is because of the word string. When n gets down to 0, there will be len stack entries being taken up by invocations of generateRecurse. There will be len stack entries at most, so the space usage of the stack will only be O(n); but each of those stack entries has its own word, which will all exist on the heap at the same time; and the lengths of those word parameters are 1, 2, ..., len, which of course do add up to (len * (len+1)) / 2, which means the space usage will be O(n2).

更多关于栈帧：看来，栈帧的基本知识的解释将是有益的......

MORE ABOUT STACK FRAMES: It appears that an explanation of the basics of stack frames would be helpful...

一个堆栈帧是的内存只是一个区域是这样的栈的一部分。典型地，堆栈pdefined的存储器区域中的$ P $;的位置和堆栈帧的大小，但是，并不pdefined $ P $。当第一次执行的程序，不会有堆栈（实际上，很可能会一些初步的数据有，但我们说没有什么，只是为了让事情变得简单）上的任何东西。所以内存的堆栈区看起来是这样的：

A "stack frame" is just an area of memory that's part of the "stack". Typically, the stack is a predefined area of memory; the location and size of stack frames, however, are not predefined. When a program is first executed, there won't be anything on the stack (actually, there will probably be some initial data there, but let's say there's nothing, just to keep things simple). So the stack area of memory looks like this:

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

（这里假定堆栈是向上增长的，从低到高的位置。许多机器堆栈生长向下。为了简化，我会继续假设这是一台机器，其堆栈向上增长的。）

(This assumes that the stack grows upward, from lower to higher addresses. Many machines have stacks that grow downward. To simplify, I'll keep assuming that this is a machine whose stack grows upward.)

当的方法（函数，过程，子例程等）被调用时，堆的某些区域被分配。该地区是足以容纳方法的局部变量（或对它们的引用），参数（或对它们的引用），一些数据使程序就知道去哪里回来时，你返回，系统和可能的其它信息 - 的其他信息是高度依赖机器，编程语言，编译器上。在Java中，第一种方法将是主

When a method (function, procedure, subroutine, etc.) is called, a certain area of the stack is allocated. The area is enough to hold the method's local variables (or references to them), parameters (or references to them), some data so that the program will know where to go back when you return, and possibly other information--the other information is highly dependent on the machine, the programming language, and the compiler. In Java, the first method will be main

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

请注意，堆栈指针上升。现在主电话方法1 。由于方法1 将返回主的局部变量和参数主必须是preserved何时主得到恢复执行。一些大小的新帧，被分配在堆栈上：

Note that the stack pointer has moved up. Now main calls method1. Since method1 will return to main, the local variables and parameters of main have to be preserved for when main gets to resume executing. A new frame, of some size, is allocated on the stack:

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

然后方法1 电话方法2 ：

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

现在方法2 的回报。经过方法2 的回报，它的参数和局部变量将无法再访问。因此，整个帧可以抛出。这是通过移动堆栈指针返回到其原来的位置进行。 （以下简称previous堆栈指针是保存在某一帧的原因之一。）堆栈将重新去是这样的：

Now method2 returns. After method2 returns, its parameters and local variables will no longer be accessible. Therefore, the entire frame can be thrown out. This is done by moving the stack pointer back to where it was before. (The "previous stack pointer" is one of the things saved in some frame.) The stack goes back to looking like this:

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

这意味着，在这一点上，机器将看到堆栈中，以堆栈指针为未使用的部分。这不是真的正确可言方法2 的帧被重用。你真的不能使用的东西已不复存在，而方法2 的框架已不复存在。从概念上讲，所有有在堆叠的一个大的空白区域。如果方法1 调用另一个方法，无论是方法2 ，方法1 递归，的System.out.println ，还是其他什么东西，一个新的框架将在栈指针现在指向的地方创建。这个框架可以在尺寸上比方法2曾经是帧是小于，等于，或更大。这会占用部分或全部，其中方法2 帧是内存。如果它是另一个调用方法2 ，这不要紧，无论它被称为具有相同或不同的参数。它不能不管，因为程序不记得什么参数被用来最后一次。所有它知道的是，存储器开始的堆栈指针的区域是空的，可以使用。该方案有不知道的帧最近住在这里。这架走了，走了，走了。

This means that, at this point, the machine will see the portion of the stack starting with the stack pointer as "unused". It's not really correct to speak of method2's frame being reused. You can't really use something that has ceased to exist, and method2's frame no longer exists. Conceptually, all there is is a big empty area of the stack. If method1 calls another method, whether it's method2, method1 recursively, System.out.println, or something else, a new frame will be created at the place where the stack pointer is now pointing. This frame could be smaller, equal, or larger in size than the method2 frame used to be. It will take up part or all of the memory where the method2 frame was. If it's another call to method2, it doesn't matter whether it's called with the same or different parameters. It can't matter, because the program doesn't remember what parameters were used last time. All it knows is that the area of memory starting with the stack pointer is empty and available for use. The program has no idea what frame most recently lived there. That frame is gone, gone, gone.

如果你可以遵循这一点，你可以看到，计算空间复杂度和时只盯着空间使用的堆栈量时，唯一重要的事情是，有多少帧可以在任何一个存在堆栈在时间点？可能已存在于过去，但不再做框架是不相关的计算，无论什么参数的方法被调用。

If you can follow this, you can see that when computing the space complexity and when looking just at the amount of space used by the stack, the only thing that matters is, how many frames can exist on the stack at any one point in time? Frames that may have existed in the past but no longer do are not relevant to the computation, no matter what parameters the methods were called with.

（PS如果有人打算要指出我是如何从技术上错误的这样或那样的细节 - 我已经知道，这是一个过于简单化）

(P.S. In case anyone was planning to point out how I'm technically wrong about this or that detail--I already know that this is a gross oversimplification.)