题12

题12

题目

Q:【2012 统考真题】求整数 的阶乘的算法如下,其时间复杂度是 ( ).

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

A.
B.
C.
D.

分析

A:这种回溯迭代的，和题10结合在一起看，先看终止条件，再看n是如何变化的，在题10里面，n为1时终止，每次n进入函数就减半，那么一共会减log2n次
这个题，终止条件是n⇐1，每次n进来会减一，那么到终止条件，就执行了n次

解

B
本题求的是递归调用的时间复杂度, 递归调用可视为多重循环, 每次递归执行的基本语句是 if return ;
因此可认为单层循环的执行次数为 1,共执行了 次递归调用,总执行次数 ,所以时间复杂度为 。