PPT《Design of Algorithms（算法设计）》

Design of Algorithms(算法设计) http://net.

pku.edu.cn/~course/cs101/2008 Hongfei YanSchool of EECS, Peking University10/31/2008 * Outline 算法的概念算法的三种基本结构算法的表示介绍几种基本算法迭代与递归 * 算法 1984年图灵奖获得者瑞士科学家尼克劳斯・沃斯(Niklaus Wirth),Pascal语言的发明者和结构化程序设计创始者1976年出版了《算法+数据结构 = 程序设计》,提出了著名的公式:"程序 = 数据结构 + 算法" .算法:解决问题的计算方法(步骤)数据结构:数据存储的模型语言:描述算法和数据结构的工具程序:用语言描述出来的算法和数据结构 * Informal definition of an algorithm used in a computer 按照这种定义,算法完全独立于计算机系统.更特别的是,还应该记住算法接收一组输入数据,并产生一组输出数据. * Finding the largest integer among five integers * Defining actions in FindLargest algorithm * FindLargest refined (精化) * Generalization (泛化) of FindLargest * 算法 is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.具有如下性质通用性:对于符合输入数据类型的任意输入数据,都能根据算法进行问题求解,并保证计算结果的正确性.能行性:算法中每条指令都是基本的,至少能够被人或机器所确定执行.确定性:每条指令必须有确切的定义,即无二义性.执行一步后,关于下一步如何执行,应该有明确的指示.有穷性:对于任意一个合法的输入,算法应在有限多步内结束,并给出计算结果. * 算法的基本要求 正确易维护(可读,易修改)方便使用高效速度快/运行时间少,时间复杂度低占用内存少/空间复杂度低 算法的效率可以测试,用大量输入数据测量运行的时间和占用的内存,通过比较判别和选择效率高的算法. 更重要的是编程前的分析和估计,即理论的计算,给出事前的判断. * 算法与数据结构关系 不了解施加于数据上的算法就无法决定如何构造数据,可以说算法是数据结构的灵魂;

反之,算法的结构和选择却常常在很大程度上依赖数据结构,数据结构是算法的基础.简而言之,程序的构成(算法)与数据结构是两个不可分割地联系在一起的问题. * Outline 算法的概念算法的三种基本结构算法的表示介绍几种基本算法迭代与递归 * 只使用如下三种结构,就可以描述任何算法,且算法结构优良顺序结构(Sequence)分支结构(Decision)循环结构(Repetition)每一种基本结构分别只有一个入口和一个出口 描述算法的三种基本结构 * 算法的表示 算法是让人来理解的,因此需要有效的算法表示机制流程图(Flowchart)表示法伪代码(Pseudocode)表达法 * Flowcharts for three constructs * Pseudocode for three constructs * Concept of a subalgorithm 采用已描述过的三种结构,可以为任何可解的问题创建算法.结构化编程的原则要求把算法分成几个单元,称之为子算法(又称为子程序、子例程、过程、函数、方法和模块).每个子算法依次又分为更小的子算法.这个过程持续到子算法变为最本质的(可被立刻理解) * 流程

图表示算法 开始/结束 处理(动作) 流程线 输入/输出 条件判断 流程图显示了程序的流程判断结构.通常包含如下符号:开始和结束流程线输入和输出处理(动作)条件判断 * 流程