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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
实验一 搜索算法问题求解
一、实验目的1.了解4种无信息搜索策略和2种有信息搜索策略的算法思想; 2.能够运用计算机语言实现搜索算法; 3.应用搜索算法解决实际问题(如罗马尼亚问题); 4.学会对算法性能的分析和比较二、实验的硬件、软件平台硬件:计算机 软件:操作系统:WINDOWS 2000 应用软件:C,Java或者MATLAB三、实验内容及步骤使用搜索算法实现罗马尼亚问题的求解 1:创建搜索树;
大步小步法解决离散对数问题 by——miskcoo
转自:http://blog.miskcoo.com/2015/05/discrete-logarithm-problem 离散对数(Discrete Logarithm)问题是这样一个问题,它是要求解模方程 ax≡b(modm)ax≡b(modm) 这个问题是否存在多项式算法目前还是未知的,这篇文章先从 mm 是质数开始介绍大步小步法(Baby
N皇后问题 - 构造法原理与证明: 时间复杂度O(1)
M皇后问题 - 构造法原理 [原] E.J.Hoffman; J.C.Loessi; R.C.Moore The Johns Hopkins University Applied Physics Laboratory [译] EXP 2017-12-29 本文完整原文下载(转载请注明出处,仅供分享学习,严禁用于商业用途) [写在前面]   这是现在网
数据抽象和问题求解-C++语言描述(第四版)源码
很难的,在国外的ftp上找到的
欧几里得算法的时间复杂度(真的没看明白)
<br />欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式                                    gcd(a, b) = gcd(b, a mod b)其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 算法如下:输入: 两个整数a, b输出: a和b的最大公约数function gcd(a, b:integer):integer;   if b=0 return a;   else
数据抽象和问题求解-Java语言描述_源代码
数据抽象和问题求解-Java语言描述_源代码 数据抽象和问题求解-Java语言描述_源代码 数据抽象和问题求解-Java语言描述_源代码 数据抽象和问题求解-Java语言描述_源代码 数据抽象和问题求解-Java语言描述_源代码
停车场问题求解(经典算法)
停车场问题求解 停车场问题求解 停车场问题求解 停车场问题求解 停车场问题求解 停车场问题求解 停车场问题求解
人工智能:复杂问题求解的结构和策略.pdf
人工智能:复杂问题求解的结构和策略.pdf
人工智能:复杂问题求解的结构和策略 PDF 高清下载
推荐理由:也是一本经典的人工智能教材,全面阐述了人工智能的基础理论,有效结合了求解智能问题的数据结构以及实现的算法,把人工智能的应用程序应用于实际环境中,并从社会和哲学、心理学以及神经生理学角度对人工智能进行了独特的讨论。
数据结构与问题求解C++版
本书是英文版,与清华影印版内容一致,是学习数据结构算法的一本较好的参考书