算法设计：第一讲

《算法设计：第一讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与复杂度计算主讲教师：徐红艳计算机系统中的任何软件（系统软件、应用软件）都是按照特定的算法来实现的。算法的好坏直接决定所实现软件性能的优劣。课程简介设计软件时需要解决的问题：（1）用什么方法设计软件（2）设计的算法需要什么样的资源（3）需要多少运行时间（4）需要多少存储空间分析算法设计与分析是计算机科学与技术的一个核心问题。课程简介设计参考教材：1、王晓东.算法设计与分析（第2版）.清华大学出版社.2、潘彦.算法设计与分析基础（第2版）.清华大学出版社.3、郑宗汉.算法设计与分析.清华大学出版社.课程简介课程的侧重点：算法设计第三章：算法设计的基本工具和优化技术第四章

2、：通用的算法设计基本策略第五章：复杂问题的算法设计策略第六章：采用不同策略解决相同问题，并进行效率分析。算法分析：对设计的算法进行时间和空间复杂度的分析。课程简介第一章算法概述人类使用计算机的目的：计算机作为工具，帮助人类求解问题。算法设计的重点：把人类找到的求解问题的方法、步骤以过程化、形式化和机械化的形式表现出来，以便让计算机执行。算法分析：是对一个算法需要多少计算时间和存储空间作定量的分析——复杂度计算。1．1用计算机求解问题与算法1．1．1用计算机求解问题的步骤人在解决问题时有很大的灵活性，对于同一个问题，不同的人有不同的经验，会采用不同的方法，如何用计算机解决一个现

3、实中的问题呢？虽然有很多不同的方法，但基本步骤是相同的。问题分析数学模型建立算法设计与选择算法表示算法分析算法实现程序调试结果整理文档编制用计算机解决一个现实中的问题步骤：1．1．1用计算机求解问题的步骤问题分析:准确、完整地理解和描述问题是解决问题的第一步。数学模型建立:用计算机解决实际问题必须有合适的数学模型。算法设计与选择:算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。1．1．1用计算机求解问题的步骤算法分析:对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题

4、的不同算法。通常将时间和空间的增长率作为衡量的标准。1．1．1用计算机求解问题的步骤算法表示：对于复杂的问题，确定算法后可以通过图形准确表示算法。算法的表示方式很多如：算法流程图、盒图、PAD图和伪码（类似于算法设计语言）等。算法实现：根据选用的程序设计语言，编写出计算机能够执行的程序。1．1．1用计算机求解问题的步骤程序调试：算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。1．1．1用计算机求解问题的步骤结果整理文档编制：编制文档的目的是让人了解你编写的算法。在

5、这些步骤中，算法设计是解决问题的核心。其次是针对设计的算法进行复杂度分析。1．1．1用计算机求解问题的步骤1．1．2算法及其要素和特性算法的定义：算法是求解某一特定问题的一组有穷规则的集合。算法的要素：操作：算术运算、关系比较、逻辑运算、数据传送（I/O，赋值等）控制结构：顺序、选择、循环控制（也称迭代）数据结构：数据的逻辑结构及存储结构1．1．2算法及其要素和特性算法的基本性质：目的性：能完成赋予它的功能分步性：由一系列计算机可执行的步骤组成有序性：不可随意改变算法步骤的执行顺序有限性：算法所包含的步骤是有限的。操作性：算法总是对某些对象进行操作，使其状态改变，完成特定功能

6、。算法的基本特征有穷性:一个算法在执行有穷步之后必须结束，而且要求运行这些步骤的时间是人们可以接受的。确定性:在任何条件下，算法都只有一条执行路径。可行性:算法中描述的操作都可以通过已经实现的基本操作运算有限次实现。输入：有零个或多个输入输出：有一个或多个输出1．1．2算法及其要素和特性1．1．3算法设计及基本方法算法设计的概念：其任务是对各类具体问题设计良好的算法。算法设计应注意的问题正确性（Correctness）可读性(Readability)健壮性（Rubustness）高效率与低存储量需求算法设计的基本方法结构化方法——“自顶向下,逐步求精”“自顶向下”是将复杂、大

7、的问题划分为小问题。“逐步求精”是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。1．1．3算法设计及基本方法面向对象方法对象=数据+对数据操作的代码实体面向对象算法设计方法的过程包括以下步骤：①在给定的抽象层次上识别类和对象②识别这些对象和类的语义③识别类和对象之间的关系④实现类和对象1．1．3算法设计及基本方法本书采用的设计方法——结构化设计方法自顶向下模块化分解过程把一个较大的算法划分为若干子算法每一个模块可继续划分为更小的子模块直到用三种控制结构和具体操作表示算法※注：运用这种编程方法，考