时间复杂度：得到不正确的结果

Question

以下代码来自“破解编码面试”一书。该代码打印字符串的所有排列。

问题：下面代码的时间复杂度是多少。

void permutation(String str) {
    permutation(str, "");
}

private void permutation(String str, String prefix) {

    if (str.length() == 0){
        System.out.println(prefix);
    } else {
        for (int i = 0; i <str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

我的理解：

我能够将时间复杂度推导出为：n * n!。

我确定我错过了蓝色、绿色和黄色节点的时间复杂度。但尽管反复尝试，始终没有明确能够找出出路。

有人可以分享一些输入，最好是例子吗？

Answer 1

您在这里的方向非常正确，并且您的总体评估（运行时间为 θ(n · n!)）是正确的！我们可以用来导出运行时的一种技术是总结树中每一层所做的工作。我们知道

• 在第 0 层（顶层），有 1 个节点处理长度为 n 的字符串，
• 在第 1 层，有 n 个节点，每个节点处理长度为 n - 1 的字符串，
• 在第 2 层，有 n(n-1) 个节点，每个节点处理长度为 n - 2 的字符串，
• 在第 3 层，有 n(n-1)(n-2) 个节点，每个节点处理长度为 n -3 的字符串，
• ...
• 在第n层，有n！每个节点处理长度为 0 的字符串。

为了说明此处完成的总工作，我们假设每个递归调用在基线上执行 O(1) 工作，再加上与其正在处理的字符串长度成比例的工作。这意味着我们需要计算两个总和来确定完成的总工作：

总和 1：调用次数

1 + n + n(n-1) + n(n-1)(n-2) + ... + n！

和

总和 2：工作处理字符串

1 · n + n · (n-1) + n(n-1)·(n-2) + ... + n！· 0

但还有另一个因素需要考虑 - 每次遇到基本情况的递归调用都会打印出以此方式生成的字符串，这需要 O(n) 时间。因此添加了最终因子 θ(n · n!)。因此，完成的总工作将是 θ(n · n!)，加上构建答案的所有中间递归调用完成的工作。

让我们分别处理这些金额。

总和 1：调用次数

我们正在处理这笔不寻常的金额：

1 + n + n(n-1) + n(n-1)(n-2) + ... + n！

我们需要的主要观察是

• 1 = n！/n!,
• n = n！/ (n-1)!,
• n(n-1) = n! /(n-2)!
• ...
• 嗯！= n！/（nn）！

所以，换句话说，这个总和是

嗯！/n！+ n！/(n-1)! + n！/(n-2)! + ... + n！/0！

= n!(1 / n! + 1/(n-1)! + 1/(n-2)! + ... + 1/0!)

≤ 恩！

= θ(n!)

在这里，最后一步源于以下事实：总和

1/0！+ 1/1！+ 1/2！+ 1/3！+ ...

无穷大是定义数字 e 的方法之一。这意味着这里的递归调用总数是 θ(n!)。

而且，直觉上，这应该是有道理的。每个递归调用，除了对长度为 1 的字符串的递归调用外，都会进行另外两次递归调用，因此递归树大部分是分支的。关于树有一个很好的事实，即每个节点都分支的树不会比叶子拥有更多的内部节点。因为有 n! 叶，剩余节点数渐近不大于 n! 也就不足为奇了。

总和 2：工作处理字符串

这是总和

1 · n + n · (n-1) + n(n-1)·(n-2) + ... + n！· 0

我们可以将其重写为

n + n(n-1) + n(n-1)(n-2) + ...

嘿！我们知道这个总和——它几乎与我们刚刚看到的一样。计算结果为 θ(n!)。

把它们放在一起

总而言之，这个递归算法确实

• θ(n!) 的工作原理仅仅是由于递归调用的数量，每个调用都需要一些基本的时间；
• θ(n!) 递归调用在形成和连接子字符串时完成的工作；和
• 最终递归调用打印出所有排列所完成的 θ(n · n!) 工作。

总结这一切给出了您在问题中提出的θ(n · n!)运行时间。

希望这可以帮助！