求整数n(n＞0)阶乘的算法如下，其时间复杂度是_______。 int fact(int n){ if(n＜=1)return 1； return n*fact(n-1)， }

admin2015-12-30 37

问题求整数n(n＞0)阶乘的算法如下，其时间复杂度是_______。
int fact(int n){
if(n＜=1)return 1；
return n*fact(n-1)，
}

选项 A、O(log₂n)
B、O(n)
C、O(nlog₂n)
D、O(n²)

答案B

解析本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是n≤1，每调用一次fact()，传入该层fact()的参数值减1。采用递归式来表示时间复杂度有

则T(n)=T(n-1)+1=T(n-2)+2=…=T(1)+n-1=O(n)，故时间复杂度为O(n)。

转载请注明原文地址:https://kaotiyun.com/show/Q7xi777K

计算机408

相关试题推荐

随机试题

最新回复(0)