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

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 适用于时间复杂度分析/em>。例如，N'th Fibonacci sequence member 的递归实现.每次调用都会终止或创建恰好 2 新的执行分支，时间复杂度将为 O(2^n)。

问题中列出的代码的递归方法调用树如下所示(左边是剩余字符，右边是前缀)。

如您所见，分支的数量从上到下递减(从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等

这就是所谓的归纳证明，有52*51*50*49*48*...*3*2*1(这是阶乘 - 52!)选择 52 的方法 牌组中的牌。

现在，您可能会认为字符串中的每个字符就像是一张卡片和字符串本身是一副大小为 n 的牌组。同样，将有 n! 方法从这个 string 中挑选所有 n characters>.

算法 - 运营成本

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

每个字符串都必须逐个字母地构造:

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

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

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

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

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

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

因此，整体时间复杂度将为O(n^2*n!)。