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

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

admin2014-12-25  33
问题 有如下递归函数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
本试题收录于： 数据结构导论题库理工类分类
0

数据结构导论

理工类

相关试题推荐
随机试题
最新回复(0)