这是我用于计算输入数组的所有排列的代码。
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 次递归调用。
帮助我如何使用数学表达式正确求解时间复杂度。
您的数学分析仅计算递归树的叶子。
要计算每个递归调用,您需要为当前调用加 1。因此,对于最深的调用,我们有 𝑇(0) = 1,对于顶层的调用,我们有:
对于 𝑛=3,这是 1 + 3 + 6 + 6 = 16,这与您在绘图中找到的内容相匹配。
但请注意,在这种情况下,递归调用的计数并不是确定时间复杂度的全部:每次执行
for
循环时,它都会迭代完整的 a
数组,因此表示 O(𝑛) 工作 no无论 if
条件有多少次为假。