数据结构-算法分析.ppt

文档介绍：算法
算法和算法分析
小结和作业
算法分析
课堂练习
hanoi(3, x,y,z)
hanoi(2, x,z,y)
hanoi(1, x,y,z)
move(x,1,z)
hanoi(1, z,x,y)
move(x,2,y)
move(x,3,z)
hanoi(2, y,x,z)
hanoi(1, y,z,x)
move(y,1,x)
move(y,2,z)
hanoi(1, x,y,z)
move(x,1,z)
move(z,1,y)
Hanoi函数的执行过程(3个)
Hanoi函数的执行过程(3个)
h(3)
h(2)
M
h(2)
h(1)
M
h(1)
M
M
h(1)
M
h(1)
M
M
算法:是为了解决某类问题而规定的一个有限长的操作序列
算法的定义
输入
输出
有穷性
确定性
可行性
算法的特点
输入:作为算法加工对象的量值,通常体现为算法中的一组变量。
输出:它是一组与“输入”有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。
算法的特点
有穷性:对于任意一组合法输入值,在执行有穷步骤之后一定能结束。即:算法中的每个步骤都能在有限时间内完成。
算法的特点
确定性:对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路径。
算法的特点
可行性:算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之。
算法的特点
算法
Algorithm:
Out = Translation(In)
计算机科学是研究解决具体问题的算法的科学。
或者,是研究信息变换的科学。