用主定理解阶乘递归算法的复杂度

上一篇提到,并非所有递推关系式都可应用支配理论。那么,递归求阶乘的算法可以用吗?

递归求阶乘算法

算法如下

int fact(int n)
{
    if(n<=1)
        return 1;
    return n*fact(n-1);
}

计算过程是 $1 \times 2 \times 3 ... \times n$,基本能直接看出来时间复杂度是 $\ O(n)$。

用主定理求解

在 CSDN 上有一篇文章[1]https://blog.csdn.net/weixin_38233103/article/details/110592111,说用主定理求此算法的时间复杂度。来试一下,递归子问题为 $a=1$ ,输入规模每次减 1,因此 b 是一个稍微大于 1 的数字,递归过程之外的步骤时间复杂度为 $\ O(1)$,则 $d=0$,则适用于 $a=b^{d}$的情况,带入主定理公式,得复杂度为 $\ O (\log{}{n})$。

显然这个结果是错误的。

主定理的适用范围

Master theorem applies only to the divide and conquer type recurrences, like T(n) = a*T(n/b) + f(n) where a is the number of subproblems and each of these subproblem's size is 1/b of the original problem. But recurrence T(n) = T(n-1) + 2 does not technically "divide" the problem into subproblems. so master theorem does not apply here[2]https://stackoverflow.com/questions/3224240/recurrence-relation-solving-big-o-of-tn-1.

递归求阶乘不是分治,不能用主定理求解。

正确的方法

递归求阶乘正确的递推式应该是 $T(n) = T(n-1) + 1$,即 需要的时间是 子问题的时间 加上 1 次乘法计算。设 $T(0) = 0$,将 $n=n-1, n=n-2, ..., n=n-n+1$ 依次带入递推式,两边求和,可得:

$$T(n) + T(n-1) + T(n-2) + ... + T(1) = T(n-1) + T(n-2) + ... + T(0) + \sum_{1}^{n} 1$$

因此:

$$T(n) = n + T(0)$$

所以复杂度是 $\ O(n)$

参考资料

参考资料
1 https://blog.csdn.net/weixin_38233103/article/details/110592111
2 https://stackoverflow.com/questions/3224240/recurrence-relation-solving-big-o-of-tn-1

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注