算法的时间复杂度
分析一个算法的好坏,时间复杂度是一个非常重要的标准。我们一般用O()表示一个算法的复杂度。
常见的算法时间复杂度有(由小到大):
O(1)常数阶 O(logn)对数阶 O(n)线性阶 O(nlogn) O(n^2) O(n^3)
| -------- p问题(时间复杂度为上) -----------|
O(2^n) O(n!)
|-NP问题(复杂度为上)-|
计算时间复杂度可分为递归和非递归两种:
举一个简单的例子:计算斐波拉契数列 f (n) = f (n-1) +f (n-2) (n < 45)
有些人第一眼看到这个问题,觉得用递归十分方便,便毫不犹豫的用了递归(这是某大学的一个考研题,很多人采用了这种算法,但是当他们将程序提交上去,在规定时间内都未能给出答案,他们都觉得不知所云),其实当我们计算过时间复杂度后,出现这个问题的原因就一目了然了。
如果我们采用递归的方式,那么我们设进入一次递归(一个基本操作)程序运行的时间为一个单位时间
故计算 T (n) = T (n-1) + T (n-2) + 1
变形 T (n) + 1 = T (n-1) + 1 + T (n-2) + 1
令 B (n) = T (n)+1
所以 B (n) = B (n-1) + B (n-2)
可见 B (n) 也是一个斐波拉契数列
所以时间复杂度 T (n) = B (n) -1 = f (n)
当n = 45 时,斐波拉契数列的值在 2,100,000,000 ,这意味着当我们计算斐波拉契的第45项时,我们要执行21亿次基本操作,这是不可想象的!!!因为在递归的过程中执行了大量的无用的重复计算!!!
如果我们采用非递归的方法递推的话,十分简单,时间复杂度为 O (n)
我在这里并不是说递归的时间复杂度一定比非递归的时间复杂度高,而是说明对于同一个问题,有不同的算法去解决这个问题,我们在之前一定要分析算法的时间复杂度。否则我们写的程序对时间的开销是不可估量的。而我们在写递归的时候,要特别注意里面嵌套了多个递归的情况。
分享到:
相关推荐
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
算法时间复杂度
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
排序算法时间复杂度的研究 期刊网站可是要现金的哦。
关于递归算法时间复杂度分析的探讨.pdf
算法时间复杂度分析基础算法时间复杂度分析基础算法时间复杂度分析基础
算法时间复杂度分析中递归方程求解方法综述
以堆排序算法为例,改变输入规模n,测试算法时间复杂度
大学二年级课程 算法设计与分析的一般算法时间复杂度的证明过程,希望可以帮到大家.
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
广度优先搜索构建迷宫(BFS算法)动态构建过程的python 源代码,详情请移步本人博客<迷宫与寻路可视化(二)广度优先搜索构建迷宫(BFS算法)>
多段图算法时间复杂度图像
所有算法时间复杂度对比、图表形式、函数关系
1. 首先产生要进行排序的整形数组(可以保存在文件中...2. 调用各种排序方法对数组排序,并记录花费时间 对于更多更高级的排序算法,以后会实现,另外,对于复杂字符串排序,这些简单排序并不适合,请采用更高效的方法
信息学奥赛算法时间复杂度和空间复杂度计算 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。 时间效率被称为时间复杂度 空间效率被称作空间复杂度
算法时间复杂度的计算.pdf
算法时间复杂度的计算.doc
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导