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

学习人数: 193

正确率: 79%

题目描述

未通过

求整数 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^2)

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

参考答案

方法一：递归式

这里分析代码...

用户登录可进行刷题及查看答案

方法一：递归式

这里分析代码需要用到递归式，递归式原则上为超纲内容，详见本题注解。

我们很容易根据算法代码写出递归式：

用递推的方式可以求解递归式： T(n)=T(n−1)+1=T(n−2)+1+1=⋯=n=O(n) 。

本题选B。

方法二：迭代

我们很容易理解代码的含义即求 n!=1×2×⋯×n 。

很容易将递归代码改写为迭代代码。

int fact(int n) {
    int f = 1;
    for (int i = 1; i <= n; i++) {
        f *= i;
    }
    return f;
}

该算法的时间复杂度为 O(n) 。

由于递归相比迭代多了一个压栈过程，所以一般情况下，迭代比递归更加高效。

本题选B。