有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n

admin2014-12-25 39

问题有如下递归函数fact(n)，分析其时间复杂度。
fact(int n)
{
if(n<=1)return(1)； ①
elsereturn(n*fact(n一1))； ②
}

选项

答案设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n一1)+O(1)，其中O(1)为运算的时间。因此 [*] 则：T(n)=O(1)+T(n一1) =2*O(1)+T(n一2) … =(n一1)*O(1)+T(1) =n*O(1) =O(n) 即fact(n)的时间复杂度为O(n)。

解析

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

本试题收录于：数据结构导论题库理工类分类