首页 > 试题广场 >

一个正整数的阶乘是从1连乘到它本身，下面递归函数实现了阶乘的

[单选题]

一个正整数的阶乘是从1连乘到它本身，下面递归函数实现了阶乘的计算，请分析出它的时间复杂度为（）

int factorial(unsigned int n)
{
    if(i <= 1)
        return 1;
    else
        return n * factorial(n-1);
}

查看正确选项

一颗会6馍的馍

emmmm不会

发表于 2022-03-10 10:27:37 回复(0)

牛客830030224号

递归的时间复杂度就是调用递归的次数

发表于 2022-11-02 14:19:50 回复(0)

WonderWu

每次递归内部计算时间为常数，所以n的阶乘，需要调用n次递归函数，时间复杂度为O(n)

发表于 2022-03-22 12:00:41 回复(0)

Warming0126

递归了多少次时间复杂度就是多少，本题调用了方法n次。时间复杂度就是n

编辑于 2024-04-01 12:45:48 回复(0)

牛客、芒果熊

f(n) = n * f(n-1) = n * (n-1) * f(n-2) = … = n * (n-1) * (n-2) *…*1，每进入一次递归函数factorial，n减小1，且每次只需要O(1)时间完成乘法和减法操作，因此总的时间复杂度为O(N)

选C

发表于 2022-11-16 10:18:48 回复(0)

牛客529111498号

运算了n-1次乘法

发表于 2022-04-14 11:25:14 回复(0)

提交观点

问题信息

复杂度递归

难度：

6条回答 79收藏 1639浏览

扫一扫，把题目装进口袋