首页 > 试题广场 >

题目来源于王道论坛求整数n(n≥0)阶乘的算法如下，

[单选题]

题目来源于王道论坛

求整数n(n≥0)阶乘的算法如下，其时间复杂度是（）。

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

查看答案及解析

推荐

林呼

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

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

发表于 2018-09-03 20:15:55 回复(4)

鸭鸭嘎嘎

时间复杂度是由语句频度分析得来. 递归算法中重复执行的语句主要是调用. 所以递归算法的时间复杂度分析主要是分析递归算法中递归函数调用的次数。

对于本题，咱们给出一个递归的图解过程，如图

从图解可知，该递归过程是线性的。总共递归执行了 n 次，时间复杂度为 O(n)。

发表于 2019-07-05 17:58:09 回复(1)

加辣椒了吗?

good

发表于 2022-02-25 13:53:20 回复(0)

提交观点

问题信息

复杂度

上传者：林呼

难度：

3条回答 131收藏 4557浏览

扫一扫，把题目装进口袋