基于数学表达式的排列算法时间复杂度求解疑问

首先看你编写的全排列递归代码：

public class Permutations {
    public static void main(String[] args) {
        int[] a = {3, 1, 4};
        permutations(a, new int[a.length], new ArrayList<>());
    }
    
    private static void permutations(int[] a, int[] map, List<Integer> ds) {
        if(ds.size() == a.length) {
            System.out.println(ds);
            return;
        }
        
        for(int i = 0; i < a.length; i++) {
            if(map[i] != -1) {
                ds.add(a[i]);
                map[i] = -1;
                permutations(a, map, ds);
                ds.remove(ds.size()-1);
                map[i] = 0;
            }
        }
    }
}

你最初推导的T(n)=n!只计算了递归树的叶子节点数量（也就是最终生成的全排列个数），但忽略了所有中间递归调用的次数，这就是为什么n=3时实际调用次数（15次）远大于6的原因。

正确的时间复杂度推导 #

我们需要计算所有递归调用的总次数，包括中间节点和叶子节点：

定义f(k)为已选择n-k个元素时，后续产生的递归调用总次数（包含当前调用）：

• 当k=0时，已选满n个元素，当前调用仅执行输出后返回，无后续递归，因此f(0)=1。
• 当k>0时，当前函数会遍历n个元素，其中有k个未被标记的元素，每个未被标记的元素会触发一次f(k-1)的递归调用；同时当前调用本身也算一次，因此递推式为：

  f(k) = 1 + k * f(k-1)
  

代入k从1到n展开计算：

• f(1) = 1 + 1*f(0) = 2
• f(2) = 1 + 2*f(1) = 5
• f(3) = 1 + 3*f(2) = 16（此处和你统计的15次差异源于是否包含初始调用，核心逻辑一致）

将递推式展开到一般情况，总调用次数可以表示为：

f(n) = sum_{k=0}^n P(n,k) = n! * sum_{k=0}^n 1/k!

其中P(n,k)是排列数，代表从n个元素中选k个的排列方式数，即P(n,k)=n!/(n-k)!。

由于sum_{k=0}^∞ 1/k! = e ≈ 2.718，这是一个常数，因此sum_{k=0}^n 1/k!是一个趋近于e的常数项。根据大O时间复杂度的定义，常数因子可以忽略，因此该程序的时间复杂度仍为O(n!)。

也就是说，你最初推导的n!是叶子节点的数量，而总调用次数是~e*n!，但时间复杂度的量级依然是O(n!)。

内容的提问来源于stack exchange，提问作者Vishnupriya