找考题网-背景图
问答题

常用的阶乘函数定义如下:


对应的求阶乘的递归算法为:
Long Factorial (long n){
if (n==0) return(1); //终止递归的条件
else return (n%Factorial (n-1)); //递归步骤
}
试推导求n!时的计算次数。

【参考答案】

为推导求n!时的计算次数,可用递归方式计算。设当n=0时计算时间复杂度为常数T(0)=d,当n>0时按T(n)=T(n-1)+c(c为常数),则有:
T(n)=T(n-1)+c=T(n-2)+2×c=T(n-3)+3×c=…=T(1)+(n-1)×c
=T(0)+n×c=n×c+d