算法引论及其简单算法_730708126.ppt

补充材料1 算法引论及简单算法
清华大学自动化系
刘连臣
2010年11月1日
计算机语言与程序设计基础
1
注意
算法是程序设计的灵魂
2
与数据结构的区别:
考虑问题的角度:数据结构关心不同的数据结构在解题中的作用和效率;算法关心不同设计技术的适用性和效率。
考虑问题的高度:数据结构关心的是解具体问题,算法不仅如此,它提供一种解决问题的通用方法。
与其他课程的关系
高级程序设计语言(C语言,等)
数据结构
算法设计与分析
系统的设计与实现
3
主要内容
目标:了解算法分析的基本含义。掌握查找算法、排序算法、递推算法等算法理念。
提纲
算法分析
查找算法
排序算法
递推算法
4
算法分析
前面的课程内容以C语言语法为主
本补充章介绍一些基本算法
大家在编写程序的时候,“八仙过海,各显神通”,解决同一个问题,可以使用各种方法。
算法之间存在着“优劣”之分
5
算法分析
1、算法分析的目的

通过对算法分析,在把算法变成程序实际运行前,就知道为完成一项任务所设计的算法的好坏,从而运行好算法,改进差算法,避免无益的人力和物力浪费。
6
算法分析
2、算法分析的含义
算法分析是一种分析技术,它以独立于具体的硬件平台、编译器和编程语言的方式,来描述算法的执行行为,即它关心的是算法,而不是程序。
算法分析是一种测量算法的性能的方法,它不关心精确的细节,如在算法的某次运行中总共执行了多少条机器指令,而是想要一个大致的估计,即随着输入数据规模的增大,算法所需工作量以何种速度递增。(关心变化趋势)
7
算法分析
3、算法复杂性
时间复杂性和空间复杂性
8
算法分析
,一旦达到这个上限,程序将被强制结束。
。
为什么要考虑时间复杂性?
9
,需指明分配给该程序的内存大小。
。
,从中择取。
。
考虑程序的空间复杂性的理由:
算法分析