1. 算法分析的评价体系
评价算法的三条主要标准是:
(1) 算法实现所消耗的时间
(2) 算法实现所消耗的存储空间,其中主要考虑辅助存储空间
(3) 算法应易于理解、易于编码、易于调试。
2. 算法的时间复杂性
2.1 和算法执行相关的因素
(1) 问题中数据存储的数据结构
(2) 算法采用的数学模型
(3) 算法设计策略
(4) 问题的规模
(5) 实现算法的程序设计语言
(6) 编译算法产生的机器代码的质量
(7) 计算机执行指令的速度
2.2 算法时间效率的衡量方法
(1) 事后分析法
先将算法用程序设计语言实现,然后度量程序的运行时间,这种方法成为事后分析法。你能想到它的缺点???
(2) 事前分析估算法
一个算法的运行工作量的大小,只依赖于问题的规模(通常用整数量n表示),或者说算法的时间效率是问题规模的函数。
假如随着问题规模n的增长,算法执行时间的增长率和函数f(n)的增长率相同,则可记作:T(n) = O(f(n)), T(n)简称时间复杂度,
O是数量级的符号。
2.3 时间复杂度估算
算法的执行时间 = $[原操作的执行次数 * 原操作的执行时间], 其中, $表示累加.
语句的频度指的是该语句重复执行的次数。
(1) 例子1
for (j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
x++;
分析: 算法段中语句"x++", "k<=n", "x++"的频度是n*n, 语句"j=1", "k=1"的频度是1, 语句"j<=n", "j++"的频度是n。
因此,算法运行的时间是3*n*n + 2*n + 2
(2) 例子2
for (j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
s++;
该算法的时间复杂度为近似n*n*n.
(3) O
在算法的复杂度分析中经常使用一个记号O,读作大O,它是数量级Order的第一个字母。当一个算法的运行时间为n*n+n+1时,
由于n*n+n+1和n*n的数量级相等(该表达式当n足够大时约等于n*n),称它为这个算法的渐进时间复杂度,简称算法的时间复杂度,
记作:T(n) = O(n*n).
(4) 几种数量级
O(1) 常数级
O(logn) 对数级
O(n) 线性级
O(n的c次方) 多项式级
O(c的n次方) 指数级
O(n!) 阶乘级
(5) 问题时间复杂度的上界和下界
(6) 算法时间复杂度的最好情况和最坏情况
2.4 算法的空间复杂性
(1) 输入数据所占空间
(2) 程序本身所占空间
(3) 辅助存储空间
分享到:
相关推荐
数据结构和算法C语言描述的全部答案,网上留传的是1-9章,我这里把1-12章全部拿出来给大家分享. 数据结构和算法C语言描述的全部答案,网上留传的是1-9章,我这里把1-12章全部拿出来给大家分享.
数据结构与算法分析C++描述分享.pdf
《数据结构与算法分析》—c语言描述_课后答案,分享给大家共同学习进步。
数据结构与算法分析—C语言描述 这是我很辛苦才找到的一本书,和大家分享了
本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具,讨论数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。
数据结构与算法分析——Java语言描述(第二版)是普林斯顿大学Mark Allen Weiss的经典之作,但是网上很少能找到Java描述第二版的课后习题,连作者的个人主页也明确表示不提供课后习题,只能到出版商那里去索取,这个...
数据结构与算法分析(带源码与习题答案),分享给需要的同学。
《数据结构与算法分析-C语言描述》很经典的数据结构与算法分析资源,给大家分享一下。
数据结构与算法分析C++语言描述第二版(Larry Nyhoff著),免费分享给大家,如果从中获益欢迎评论,谢谢
数据结构 算法 算法分析 C++ 描述(第3版)好不容易找到的,分享一下,好东西呦。
数据结构与算法分析Java语言描述(第2版),很经典哒,免费分享!