算法和算法分析.ppt

.com,.,,.,.,.,.cn,,防腐剂(Algorithm):算法是一个有限的指令集,遵循指令流可以完成特定的功能。:有穷性:算法经有限步后结束;确定性:每一步必须是确切的;可行性:每一步是可执行的;输入:有0或多个输入值;输出:有1或多个输入值;:有穷性:算法经有限步后结束;确定性:每一步必须是确切的,即在任何条件下,算法都只有一条执行路径。菜谱中“加入食盐少许”,少许是不确切的;如果A<3则做A+B,如果A>6则做A-B;可行性:每一步是可执行的,相当基本的,都可以通过已经实现的基本运算执行有限次来实现之;,考虑如何将输入转换成输出,一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。主要区别在:有穷性、正确性和描述方法程序可以是无穷的,例如OS,算法是有穷的;程序可以是错误的,算法必须是正确的;程序是用程序设计语言描述,在机器上可以执行;算法还可以用框图、自然语言等方式描述。、算法的描述和实现描述---可采用自然语言、数学语言或约定的符号语言。实现---必须借助程序设计语言提供的数据类型及其运算。本课的描述---采用类C语言。:设计技术:如何设计一个有效的算法分析技术: 如何衡量一个算法的好坏? 衡量的四个尺度:正确性:问题的任何一个实例作为输入,算法都能得到正确的结果作为输出;时间特性:运行所花费的时间;空间特性:所占用存储空间的大小;其他(可读性、易调性、健壮性等)。 时间和空间特性的巨大改进源于更好的数据结构或算法。(操作系统、编程语言和编译系统),下面几种度量算法的时间特性的方法被废弃:算法运行的实际执行时间运行过程中所执行的指令条数运行过程中程序循环的次数算法的时间特性用执行基本操作次数来度量。:是指算法运行中起主要作用且花费最多时间的操作。例如:实数矩阵乘法中,基本操作为实数元素之间的数乘;N个整数排序中,基本操作可以是整数间的比较或数据元素的移动;:是指算法运行中,输入的规模。例如:实数矩阵乘法中,问题规模为矩阵的阶数(n阶方阵);排序问题中,问题规模是待排序元素个数;