使用数学表达式解释排列的时间复杂度

Question

这是我用于计算输入数组的所有排列的代码。

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*T(n-1)
     = n*[(n-1)*T(n-2)]
     = n*(n-1)*(n-2)*--*T(0)
     = n!

所以，我得到了n！使用我的数学表达式，但我看到递归树中正在进行更多数量的递归调用。

对于 n = 3，n!= 6，其中递归树有 15 次递归调用。

帮助我如何使用数学表达式正确求解时间复杂度。

Answer 1

您的数学分析仅计算递归树的叶子。

要计算每个递归调用，您需要为当前调用加 1。因此，对于最深的调用，我们有 𝑇(0) = 1，对于顶层的调用，我们有：

• 𝑇(𝑛) = 1 + 𝑛𝑇(𝑛−1)
• 𝑇(𝑛) = 1 + 𝑛(1 + (𝑛−1)𝑇(𝑛−2))
• ...
• 𝑇(𝑛) = 1 + 𝑛 + 𝑛(𝑛−1) + 𝑛(𝑛−1)(𝑛−2) + ... + 𝑛！

对于 𝑛=3，这是 1 + 3 + 6 + 6 = 16，这与您在绘图中找到的内容相匹配。

但请注意，在这种情况下，递归调用的计数并不是确定时间复杂度的全部：每次执行

for

循环时，它都会迭代完整的

a

数组，因此表示 O(𝑛) 工作 no无论

if

条件有多少次为假。