首页 > 试题广场 >

下面函数的时间复杂度是

[单选题]
下面函数的时间复杂度是 
long foo(long x){
    if(x < 2) return 1;
        return x * x * foo(x - 1);
}
  • O(N)
  • O(N^2)
  • O(N^3)
  • o(N!)
查看正确选项
添加回答
牛客183660号头像 牛客183660号
可以配合自己画的流程图看
x=1    O(1)
x=2    O(1+O(foo(1)))=O(2)
x=3    O(1+O(foo(2)))=O(3)
。。。依次类推
x=N    O(1+O(foo(N-1)))=N
发表于 2015-09-04 17:01:20 回复(0)
IreanLau头像 IreanLau
递归
    时间复杂度：递归次数
    空 间复杂度：递归深度（调用栈帧）

发表于 2016-04-09 19:08:56 回复(2)
Leo_LWF头像 Leo_LWF 
当n>=2时
foo(n)=n^2*foo(n-1)=n^2*(n-1)^2*foo(n-2)=...=n^2*(n-1)^2*...*2*foo(1);
递归n-1步，时间复杂度为O(n)。

发表于 2015-09-05 16:13:36 回复(0)
牛客474535号头像 牛客474535号
这里要从foo(1)一直计算到foo(n)，因此时间复杂度为O(N)
发表于 2015-09-02 10:05:17 回复(3)
R0b1n头像 R0b1n
从结构上可以看出
需要使用分治法来解递归式
分解(Divide)：规模为n的主问题分解为规模n-1的子问题，计算n-1的值需要常量时间O(1)
解决(Conquer)：每次分解产生1个子问题，即产生T(n-1)的消耗
合并(Merge)：
每次合并只需要执行一个语句  
 (x^2)*T(n-1)
注意最后规模为1时的合并需要特殊考虑，观察到其也只有一个语句 
 return 1;
所以 所有合并操作都只需要常量时间O(1)

将分解与合并所需的时间消耗相加  
 O(1)+O(1) = O(1)
于是可以归纳出该算法的递归式 
T(n) = T(n-1) + O(1)
其中T(n)为总时间
T(n-1)为分解后的子问题所需的时间
O(1)为上文计算出的分解与合并子问题所需的时间

根据主方法，此递归式中的b==1，所以不属于主方法的适用范围
改用代数法求解
观察可知 
T(n) = T(n-1) + O(1)
T(n-1) = T(n-2) + O(1)
......
T(2) = T(1) + O(1)
T(1) = O(1)
将所有等式的左值分别相加，右值分别相加，得 
T(1)+...+T(n) = T(1)+...T(n-1) + n*O(1)
同项相消得 
T(n) = n*O(1) = O(n)

编辑于 2017-09-28 12:15:32 回复(0)
starnight_cyber头像 starnight_cyber
这个要看foo(x)里参数的变化啦，由 x -> x-1，直到参数变成常数2时返回， 时间复杂度跟x线性相关，故时间复杂度为O(N)
发表于 2016-08-26 20:26:33 回复(0)
菩提旭光头像 菩提旭光
一看时间复杂度就是线性的。所以自然而然的就是A选项了。
编辑于 2015-09-04 21:02:08 回复(1)
FLYFREELY头像 FLYFREELY
有木有错选D（阶乘）的
发表于 2023-08-24 11:15:31 回复(0)
牛客189678898号头像 牛客189678898号
时间复杂度与递归次数成正比
发表于 2022-01-19 10:05:08 回复(0)
sky_头像 sky_
等价于for(int i=1;i<=n;i++) ans*=i*i;,明显的线性。
发表于 2017-08-09 14:34:54 回复(0)
牛客210468号头像 牛客210468号
longfoo(longx){
    if(x<2) return1;
        returnx*x*foo(x-1);
}
程序运行了n此，所以时间复杂度就是O(N)
发表于 2015-09-13 17:09:16 回复(0)
牛客143068号头像 牛客143068号
递归
    时间复杂度：递归次数
    空 间复杂度：递归深度（调用栈帧）

计算：
x=1    O(1)
x=2    O(1+O(foo(1)))=O(2)
x=3    O(1+O(foo(2)))=O(3)
。。。依次类推
x=N    O(1+O(foo(N-1)))=N

发表于 2020-07-16 11:08:22 回复(0)
午睡到凌晨头像 午睡到凌晨
里面有for循环时间复杂度还是n吗？long foo(long x){ if(x<2) return 1; for(i=0;i
发表于 2019-11-06 23:18:52 回复(0)
牛客网买房的小郑头像 牛客网买房的小郑
递归 递归的时间复杂度为递归的次数
发表于 2018-09-13 23:25:45 回复(0)
Aidous*头像 Aidous*
最坏执行n次
发表于 2018-03-09 09:09:58 回复(0)
qq_w头像 qq_w
时间复杂度即为递归的次数，即，foo(n-1)到f(1)的计算次数
发表于 2016-10-11 10:24:08 回复(0)
牛客9224710号头像 牛客9224710号
复杂度不熟悉
发表于 2016-06-28 09:21:33 回复(0)
Basstal头像 Basstal
计算时间复杂度不太会
发表于 2016-04-21 23:53:04 回复(0)
牛客265482号头像 牛客265482号
当n>=2时
foo(n)=n^2*foo(n-1)=n^2*(n-1)^2*foo(n-2)=...=n^2*(n-1)^2*...*2*foo(1);
递归n-1步，时间复杂度为O(n)。
发表于 2016-04-01 10:23:27 回复(0)
谭锅锅头像 谭锅锅
最简答的方法就是那个小一点的数试一下就行了
发表于 2015-12-26 20:53:10 回复(0)
提交观点

问题信息

C语言 C++
来自：腾讯2016研发工程师...
难度：
29条回答 13997浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号