摘要: 算法是为某种计算设计的某个问题的解决方法。不同算法可能会用不同的时间、空间效率来完成同样的任务。一个算法的优劣基本上可以用空间复杂度与时间复杂度来衡量。其中时间复杂度是最主要的衡量标准。算法的经验分析是指将设计的算法用程序语言实现后,在具体的计算机上运行,并记录不同规模的数据所运行的时间,通过记录的数据来分析算法的时间复杂度。
本文深刻分析了欧几里得算法,汉诺塔问题算法,快速排序算法、冒泡排序算法、希尔排序算法等排序算法,对这些算法的效率进行了经验分析,并得到了一些结论。
关键词 算法;效率;复杂度;经验分析
目录
摘要
Abstract
1 绪论-1
1.1 课题背景-1
1.2 研究内容-1
1.3 技术路线-1
1.4 本文组织结构-1
2 算法效率经验分析-3
2.1算法效率经验分析框架-3
2.1.1输入规模的度量-3
2.1.2运行时间的度量-3
2.1.3数学分析和算法经验分析的区别-3
2.2渐进符号和基本效率类型-4
2.2.1渐进符号-4
2.2.2基本效率类型-4
2.3对算法效率做经验分析的常用方案-4
3汉诺塔算法效率经验分析-7
3.1汉诺塔算法原理-7
3.2汉诺塔算法代码实现-7
3.3汉诺塔算法效率经验分析-8
4欧几里德算法效率经验分析-11
4.1欧几里德算法原理-11
4.2欧几里德算法各指标分析-11
4.3欧几里德算法效率经验分析-12
5排序算法的效率经验分析-14
5.1冒泡排序-14
5.1.1冒泡排序原理-14
5.1.2冒泡排序实现与效率经验分析-14
5.2希尔排序-16
5.2.1希尔排序原理-16
5.2.2希尔排序实现与效率经验分析-17
5.3快速排序-21
5.3.1快速排序原理-21
5.3.2快速排序实现与效率经验分析-21
5.4各排序算法比较-25
6总结-28
致谢-29
参考文献-30
附录-31