2 qq 23660243 qq_23660243 于 2016.02.18 15:31 提问

时间复杂度问题求解明白

Int fact(int n)
{if (n<=1)
return 1;
return n*fact(n-1);
}
A. O(log2n) B. O(n) C . (a log2n) D. O(n2)
为什么是B 我不是很明白 n的阶乘按理说不是n(n-1)吗 那么时间复杂度应该是D呀

5个回答

leilba
leilba   Rxr 2016.02.18 15:41
已采纳

时间复杂度可以简单看成主要工作单元的调用的次数,比如说你题的主要工作单元是:n*fact(n-1),那么实际在整个运行中,调用的次数为 n-1次,那么复杂度取 0(n)。

qq_23660243
qq_23660243 感谢 懂了
接近 2 年之前 回复
henuyx
henuyx   2016.02.18 16:49

for (i =0; i < n; i ++)
{
for(j =0; j < n; j+++)
{..................}
}

这个的复杂度才是N^2

qq_23660243
qq_23660243 感谢 懂了
接近 2 年之前 回复
Mr_dsw
Mr_dsw   Ds   Rxr 2016.02.18 22:03

他只是一个递归,算法的复杂度并没有变

qq_23660243
qq_23660243 感谢 懂了
接近 2 年之前 回复
lm_whales
lm_whales   Rxr 2016.02.19 01:04

时间复杂度和主要操作认定有关

递归调用成功的把 主要操作由乘法,转换为函数调用
时间复杂度没变,效率降低了

qq_23660243
qq_23660243 感谢 懂了
接近 2 年之前 回复
lm_whales
lm_whales 编译器可以优化尾递归,经过优化的效率没降低,但不保证编译器足够聪明,可以优化递归调用
接近 2 年之前 回复
devmiao
devmiao   Ds   Rxr 2016.02.19 04:37
 这是尾递归,相当于
while (n > 1)
r = r*n--;
return r;
所以是On
qq_23660243
qq_23660243 感谢
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!