同一个问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
对一个算法的性能的评价主要从时间复杂度
和空间复杂度
来考虑,二者合称为算法复杂度
。
1、时间复杂度
(1)时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度
在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度的概念。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n), 使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)), 称O(f(n))为算法的渐进时间复杂度
,简称时间复杂度。O是数量级的符号。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1)。另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
按数量级递增排列,常见的时间复杂度有:
常数阶
|
对数阶
|
线性阶
|
线性对数阶
|
平方阶
|
立方阶
|
……
|
K次方阶
|
指数阶
|
O(1)
|
O(log2
n
)
|
O(n)
|
O(nlog2
n)
|
O(n2
)
|
O(n3
)
|
|
O(nk
)
|
O(2n
)
|
复杂度低 ---->---->---->---->---->---->---->---->---->---->---->---->----> 复杂度高
随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
2、空间复杂度
与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:
S(n)=O(f(n))
我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。
---------------------------------------------------------------------------------------------------------------------------------
常用的算法的时间复杂度和空间复杂度:
排序法
|
平均时间
|
最差情形
|
稳定度
|
额外空间
|
备注
|
冒泡
|
O(n2
)
|
O(n2
)
|
稳定
|
O(1)
|
n较小时较好
|
交换
|
O(n2
)
|
O(n2
)
|
不稳定
|
O(1)
|
n较小时较好
|
选择
|
O(n2
)
|
O(n2
)
|
不稳定
|
O(1)
|
n较小时较好
|
插入
|
O(n2
)
|
O(n2
)
|
稳定
|
O(1)
|
大部分已排序时较好
|
基数
|
O(logR
B)
|
O(logR
B)
|
稳定
|
O(n)
|
B是真数(0-9),
R是基数(个十百)
|
Shell
|
O(nlogn)
|
O(ns
) 1<s<2
|
不稳定
|
O(1)
|
s是所选分组
|
快速
|
O(nlogn)
|
O(n2
)
|
不稳定
|
O(nlogn)
|
n较大时较好
|
归并
|
O(nlogn)
|
O(nlogn)
|
稳定
|
O(1)
|
n较大时较好
|
堆
|
O(nlogn)
|
O(nlogn)
|
不稳定
|
O(1)
|
n较大时较好
|
(引用自:各种排序的稳定性和复杂度小结
)
分享到:
相关推荐
算法的空间复杂度是指算法程序中指令(或语句)的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对- (2) 以下数据结构中不属于线性数据结构的是(C)- A. 队列 B. 线性表 C. ...
【考点2】算法的复杂度 【考点3】数据结构的基本概念 【考点4】逻辑结构和存储结构 【考点5】线性结构和非线性结构 【考点6】线性表及其顺序存储结构 【考点7】线性链表 【考点8】栈 【考点9】队列 【考点10】树的...
(二)算法设计的基本要求 (三)语句的频度和估算时间复杂度 二、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 三、栈、队列和数组 (一)栈和队列的基本概念 (二)...
这份试题集主要覆盖了数据结构课程内容的核心部分,包括基本数据结构、树与图、排序和查找算法以及复杂度分析等方面。所有试题都采用了清晰简洁的语言描述,并配合详细的解答,使得你可以轻松理解并牢记各种算法思想...
并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1、数据结构(1)基本数据结构数据结构基本概念(时间复杂度和空间复杂度的计算方法)数组链表集合队列栈关联数组跳表倒排索引BitSet(2)树...
时空复杂度,大 O 表示法 原地算法 数据结构 几大排序算法 由浅入深的大致顺序 数组,字符串 链表 递归 栈,队列 分治法 贪心法 动态规划 树、图 BFS、DFS 参考资料 (大致整理) 书 Repo 专题 数组和字符串 (21/21)...
12_构造和析构的重点整理 13_构造和析构总结 14_中午课程复习 15_构造函数的调用规则研究 16_浅拷贝问题抛出 17_浅拷贝问题分析_传智扫地僧 18_浅拷贝问题解决_深拷贝_显示编写拷贝构造函数 19_深拷贝和浅拷贝_默认...
(2)在相同的规模 n下,复杂度O(n)的算法在时间上总是优于复杂度 O(2 n)的算法 (3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B...
D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:在非递减有序的单链表中删除值相同的多余...
2.3 传统离群点检测的缺点: 基于统计的算法:不适合多维空间,预先要知道样本空间中数据集的分布特征 基于距离的算法:参数的选取⾮常敏感,受时间复杂度限制,不适⽤于⾼维稀疏数据集。 基于偏差的算法:实际应⽤...
本文大量的工作基于《人工智能写作指南v1.0》,结合近些年作者的实践研究及国内外行业进展,整理而成,主要包括知识点、产品、技术栈等内容。 版本记录:2019-02-14 v1.02020-04-26 v2.0 - 背景 这是一个机器人写稿...
答:“软件危机”(Software Crisis)的出现是由于软件的规模越来越大,复杂度不断增 加,软件需求量增大。而软件开发过程是一种高密集度的脑力劳动,软件开发的模式及技术 不能适应软件发展的需要。致使大量质量低劣...