为什么置换函数的时间复杂度是 O(n!)

Question

考虑以下代码。

public class Permutations {
    static int count=0;
    static void permutations(String str, String prefix){
        if(str.length()==0){
            System.out.println(prefix);
        }
        else{
            for(int i=0;i<str.length();i++){
                count++;
                String rem = str.substring(0,i) + str.substring(i+1);
                permutations(rem, prefix+str.charAt(i));
            }
        }

    }
    public static void main(String[] args) {
        permutations("abc", "");
        System.out.println(count);
    }

}

这里的逻辑，我认为遵循的是——它将字符串的每个字符视为一个可能的前缀，并排列剩余的 n-1 个字符。
所以按照这个逻辑递归关系是

T(n) = n( c1 + T(n-1) )          // ignoring the print time

这显然是 O(n!)。但是当我使用一个计数变量来查看小麦算法真的按照 n! 的顺序增长时，我发现了不同的结果。
对于 count++ 的 2 长度字符串（在 for 循环内）运行s 4 次，对于 3 长度的字符串，count 的值为 15，对于 4 和 5 长度的字符串，其值为 64 和 325。
这意味着它变得比 n! 更糟。那么为什么它说这个（以及产生排列的类似算法）在运行时间方面是 O(n!)。

Answer 1

人们说这个算法是 O(n!) 因为有 n! 排列，但你在这里计算的是（在某种意义上）函数调用 - 而且函数调用比 n!:

当 str.length() == n 时，您进行了 n 次调用；
对于这些 n 次 str.length() == n - 1 次调用，您进行了 n - 1 次调用；
对于每个 n * (n - 1) 调用 str.length() == n - 2，您都会进行 n - 2 调用；
...

您使用长度为 k¹ 的输入 str 执行 n! / k! 调用，并且由于长度从 n到0，调用总数为：

sum _{k = 0 ... n} (n! / k!) = n! sum _{k = 0 ... n} (1 / k!)

但是你可能知道：

sum _{k = 0 ... +oo} 1 / k! = e¹ = e

所以基本上，这个总和总是小于常量 e（并且大于 1），所以你可以说调用次数是 O(e.n!)，即 O(n!).

运行时复杂度通常不同于理论复杂度。在理论上的复杂性中，人们想知道排列的数量，因为算法可能会检查这些排列中的每一个（因此实际上已经完成了 n! 检查），但实际上还有更多事情在发生。

_{¹ 这个公式实际上会给你一个与你得到的值相比的值，因为你没有考虑初始函数调用。}

Answer 2

这个答案适合像我这样不记得 e=1/0!+1/1!+1/2!+1/3!...

我可以用一个简单的例子来解释，假设我们想要 "abc"

的所有排列

        /    /   \     <--- for first position, there are 3 choices
       /\   /\   /\    <--- for second position, there are 2 choices
      /  \ /  \ /  \   <--- for third position, there is only 1 choice

上面是递归树，我们知道有3!个叶子节点，代表了"abc"所有可能的排列（也就是我们 对结果执行操作，即 print())，但由于您要计算所有函数调用，我们需要知道总共有多少树节点（叶子 + 内部)

如果它是一个完整的二叉树，我们知道有 2^n 个叶节点...有多少个内部节点？

x = |__________leaf_____________|------------------------|  
let this represent 2^n leaf nodes, |----| represents the max number of
nodes in the level above, since each node has 1 parent, 2nd last level
cannot have more nodes than leaf
since its binary, we know second last level = (1/2)leaf 
x = |__________leaf_____________|____2nd_____|-----------|
same for the third last level...which is (1/2)sec
x = |__________leaf_____________|____2nd_____|__3rd_|----|

x 可以用来表示树节点的总数，因为我们总是在初始 |-----| 上减半，我们知道 total <= 2*leaf

现在用于置换树

x = |____leaf____|------------|
let this represent n! leaf nodes
since its second last level has 1 branch, we know second last level = x 
x = |____leaf____|____2nd_____|-------------|
but third last level has 2 branches for each node, thus = (1/2)second
x = |____leaf____|____2nd_____|_3rd_|-------|
fourth last level has 3 branches for each node, thus = (1/3)third
x = |____leaf____|____2nd_____|_3rd_|_4|--| |
| | means we will no longer consider it

这里我们看到 total < 3*leaf，这符合预期 (e = 2.718)

为什么置换函数的时间复杂度是 O(n!)

Why Time complexity of permutation function is O(n!)

algorithm

permutation

time-complexity