如何使用递归树估计生成字符串排列的时间复杂度

Question

以下代码打印字符串的所有排列：

void permutation(String str) {
    permutation(str, "");
}
    
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));
        }
    }
}

GeeksForGeeks通过判断分析代码的时间复杂度：

该函数在其基本情况下被调用 n! 次
for 循环运行 n 次
因此，递归树中的阶乘节点不会超过 n * n! 个。
每个函数调用对应O(n)个工作，因此总时间复杂度为O(n² * n!).

我知道可以通过将递归树中的节点数乘以每个函数调用所做的工作量来估算时间复杂度。如果我使用公式 branches^depth 来估计递归树中的节点数，我在递归树中得到 nⁿ 个节点，这与 n * n!.

完全不同

我想知道为什么 branches^depth 不是这个问题的严格限制，在这种情况下我不应该使用 O(branches^depth) 来估计进行多次调用的函数的时间复杂度。

Answer 1

递归调用树

公式branches ^ depth适用于time-complexity分析，每次递归调用产生相同数量的分支。例如，N'th Fibonacci sequence member 的递归实现。每次调用终止或创建 恰好 2 新分支 执行并且时间复杂度将为 O(2^n) .

问题中列出的代码的递归方法调用树如下所示（左侧为剩余字符，右侧为前缀）。

可以看到，branches的个数从上到下递减（从n到1), 因为字符数还没有被使用

排列

长度n的给定String的排列的数量是n!。

让我们用一个简单的例子来探讨为什么。

假设您需要从尺寸为 52 的标准牌组中挑选 1 张牌. IE。有 52 种可能性可供选择。

第一张牌选好后，需要选择下一张，有51的方法做出这个选择。

也就是说2张牌的总取法数是52*51.

那么，对于第三张牌，我们的牌组中只剩下50张牌。

这意味着有 52*51*50 种方法可以从牌组中选择 3 张牌。

对于四张牌，该数字将为52*51*50*49，对于五张 ] - 52*51*50*49*48,等等。

这是一个so-called归纳证明有52*51*50*49*48*...*3*2*1（这是阶乘 - 52!) 从牌组中挑选 52 牌的方法。

现在，您可能会认为 字符串 中的每个字符就好像它是一张卡片并且 string 本身是 deck 大小 n。同样，将有 n! 方法从这个 string[= 中选择所有 n characters 146=].

算法 - 运营成本

由于排列的数量是n!，这意味着我们需要生成n! 字符串长度 n.

每个字符串必须逐个字母构造：

prefix + str.charAt(i) // append a charactor at position `i` to the `prefix` string

为了创建长度为 n 的 字符串 ，我们需要选择一个字符 n循环中的时间。迭代的每一步都会产生一个递归方法调用。因此，将需要 n*n! 方法调用来构造所有 n! 排列 .

有一个额外的成本会增加总时间复杂度。

创建剩余字符串（尚未选取的字符）需要调用

str.substring(0, i) + str.substring(i + 1)

在每次方法调用时。这将花费 O(n) 时间，因为为了创建一个子字符串，我们迭代了源字符串并将最多 n - 1 个字符从其底层数组复制到新的字符串.

因此整体的时间复杂度会是O(n^2*n!).

Answer 2

正如评论中@rici所建议的那样，当节点的分支数根据递归而变化时，branches^depth 似乎不是一个好的估计深度，如本题所示。

对于这个问题，似乎更好的估计节点数的方法是使用@Shubham here描述的公式：

Complexity = length of tree from root node to leaf node * number of leaf nodes

当我为一个长度为n的字符串绘制这个函数的递归树时，我看到有n个！叶节点。递归的深度为n，所以节点总数为n * n!。正如问题中提到的，由于每个函数调用对应于 O(n) 工作，因此总时间复杂度为 O(n² * n!).

如何使用递归树估计生成字符串排列的时间复杂度

How to estimate the Time Complexity of generating string Permutations using Recursion tree

java

algorithm

recursion

time-complexity

permutation

递归调用树

排列

算法 - 运营成本