algorithm - 为什么置换函数的时间复杂度是 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 循环内)运行 4 次，对于 3 长度的字符串，count 的值是 15，对于 4 和 5 长度的字符串，其值为 64 和 325。
这意味着它变得比 n! 更糟。那么为什么它说这个(以及生成排列的类似算法)在运行时间方面是 O(n!)。

Answer 1

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

• 当 str.length() == n 时，您执行 n 次调用；
• 对于每个使用 str.length() == n - 1 的 n 调用，你执行 n - 1 调用；
• 对于每个 n * (n - 1) 调用 str.length() == n - 2 你做 n - 2调用；
• ...

你做 n!/k! 使用长度为 k¹ 的输入 str 调用，并且由于长度从 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! 检查完成)，但实际上还有更多的东西继续。

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