javascript - 如何确定这个算法的时间和空间复杂度？

Question

在准备即将到来的面试时，我研究了字符串排列问题。 -

问题陈述 - 编写一个函数来生成输入字符串的所有排列。

这是我觉得还不错的解决方案。

function getPermutations(string) {

    // base case
    if (string.length <= 1) {
        return new Set(string);
    }

    var allCharsExceptLast = string.slice(0, -1);
    var lastChar = string[string.length - 1];

    // recursive call: get all possible permutations for all chars except last
    var permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);

    // put the last char in all possible positions for each of the above permutations
    var permutations = new Set();
    permutationsOfAllCharsExceptLast.forEach(function(permutationOfAllCharsExceptLast) {
        for (var position = 0; position <= allCharsExceptLast.length; position++) {
            var permutation = permutationOfAllCharsExceptLast.slice(0, position) + lastChar + permutationOfAllCharsExceptLast.slice(position);
            permutations.add(permutation);
        }
    });

    return permutations;
}

即使我理解解决方案(我尝试了几次并获得了大约一百万个控制台日志)，递归还是让我感到困惑。有人可以为我分解时间和空间的复杂性吗？

Answer 1

让我们想想这个过程。假设我们的字符串是 n 个字符长。首先，我们必须传递字符串中的每个字符(n 操作)，然后对于每个字符，递归地生成字符串中其他 n-1 个字符的排列，我们将从中为每个第二个字符递归地生成字符串中 n-2 个字符的排列，依此类推......直到只剩下 1 个字符。为了计算总时间复杂度，我们将所有这些项相乘 (n * (n-1) * (n-2) * ... * 1 = n!)，得到时间复杂度O(n!) 的大 O 表示法。

为了思考为什么要将它们相乘，我们可以考虑如下更简单的问题:如果我们有 2 条裤子和 3 件衬衫，有多少种不同的衣服可以穿。答案显然是六，我们通过注意到对于每件衬衫，我们有两种裤子选择得到这个，所以我们用衬衫的数量乘以裤子的数量。

我们可以将这个例子翻译成一个简单的字符串，比如单词“cat”。要获得每个排列，您的代码首先选择一个字符(选择字符的顺序无关紧要，因此我将首先选择“c”)，然后在剩余的字符串中找到排列，在本例中为“at ”。唯一的两个排列是“at”和“ta”是微不足道的，因此我们将字符串“atc”和“tac”添加到整体排列中。接下来，我们取出'a'，剩下的String就是“ct”，从中排列出来就是“ct”和“tc”。因此，我们将“cta”和“tca”添加到我们的整体排列中。最后，当我们取出“”时做同样的事情，我们最终得到“ca”和“ac”作为我们剩余的排列，所以我们将“cat”和“act”添加到我们的整体排列中，我们就完成了。请注意，在这种情况下，它们都是唯一的，但如果一个字母被重复(例如“wow”)，那么您的算法将重复计算，这没关系，因为这并不是真正需要考虑的。

无论如何，希望这对您有所帮助，如果您还有其他问题，请发表评论。