算法设计一.pptVIP

课程目的：计算机算法设计与分析导引 以算法设计为主，介绍算法设计的主要方法和基本思想；并简要介绍算法分析概念 不是程序设计课，也不是数学课 主要内容： 算法复杂性分析 方法：蛮力法、递归与分治、减治法、动态规划、贪心法。 第1章 算法概述 本章主要知识点： 1.1 算法与程序 1.2 算法问题求解基础 1.3 重要问题类型 1.4 基本数据结构 1.5 算法分析的基本原则 1.6 算法复杂性分析 1.1 算法与程序 算法：是满足下述性质的指令序列。 输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 程序： 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。 1.1 算法与程序 算法的概念 问题 ↓ 算法 ↓ 输入→computer →输出 同一算法可以用几种不同的形式来描述 同一问题，可能存在几种不同的算法，不同算法解题速度也会有所不同。 例子：求两个不全为0的非负整数m和n的最大公约数记为gcd(m,n) 欧几里德算法 //输入：两个不全为0的非负整数m, n //输出： m, n的最大公约数 While n≠0 do r←m mod n m ←n n ←r Return m 中学里学过的计算方法 找到m, n的所有质因数 从上述质因数分解式中找出所有公因数（如果p是一个因数，而且在m和n的质因数分解式中分别出现x和y次，则将p重复min{x.y}次 将上述找到的质因数相乘，其结果作为最大公约数 1.2 算法问题求解基础 算法＋数据结构＝程序 算法设计分析的主要步骤 理解问题 了解计算设备的性能 在精确算法和近似算法之间做出选择 确定适当的数据结构 算法的设计技术 算法的描述（伪代码） 算法的正确性证明 算法的分析（简单性、一般性） 1.3 重要问题类型 排序 查找 字符串处理 图问题（图的遍历算法、最短路线算法、图着色问题） 组合问题 几何问题（最接近点对问题、凸包问题） 数值问题（具有连续性的数学问题：解方程、定积分、求函数值） 1.4 基本数据结构 数据结构：对相关的数据项进行组织的特殊方案。 算法与数据结构的关系 不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂； 反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。 线性数据结构（数组和链表）、图（加权图、路径和环）、树（有根数、二叉树）、集合与字典 1.4 表达算法的抽象机制 抽象数据类型 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： 算法顶层设计与底层实现分离； 算法设计与数据结构设计隔开，允许数据结构自由选择； 数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； 用抽象数据类型表述的算法具有很好的可维护性； 算法自然呈现模块化； 为自顶向下逐步求精和模块化提供有效途径和工具； 算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 1.4 描述算法与算法设计 问题求解(Problem Solving) 1.5 算法分析的基本原则 正确性 定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。 正确性证明的内容： 方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。 程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。 程序正确性证明的方法： 大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。 小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。 1.5 算法分析的基本原则 工作量——时间复杂性分析 计量工作量的标准: 对于给定问题，该算法所执行的基本运算的次数。 基本运算的选择：根据问题选择适当的基本运算。 1.5 算法分析的基本原则 占用空间——空间复杂性分析 两种占用： 存储程序和输入数据的空间 存储中间结果或操作单元所占用空间——额外空间 影响空间的主要因素： 存储程序的空间一般是常数(和输入规模无关) 输入数据空间为