《算法课件2015第1章绪论》由会员分享，可在线阅读，更多相关《算法课件2015第1章绪论（61页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析,马志强 EMAIL: 地点: 21B软件学院教师办公室 课件下载地址 http:/ 年代前 计算机科学基础的主题没有被清楚地认清。 70 年代 Knuth 出版了The Art of Computer Programming 以算法研究为主线 确立了算法为计算机科学基础的重要主题 Knuth 于1974 年获得图灵奖。 70 年代后 算法作为计算机科学核心推动了计算机科学技术飞速发展,算法是计算机科学的主题,3,解决一个计算问题的过程,计算机科学体系与算法的地位,可计算否,能行可计算否,算法设计与分析,可计算理论 计算模型 可计算问题/不可计算问题 计算模型的等价性 计
2、算复杂性理论 给定模型下问题的复杂性，复杂性问题的分类: P=NP?，抽象复杂性 算法设计和分析 可计算问题算法的设计与分析，理论、方法和技术 计算机软件 系统软件，工具 软件，应用软件,计算机科学体系,用计算机语言实现算法,4,计算机科学体系与算法的地位,可计算否,能行可计算否,算法设计与分析,用计算机语言实现算法,解决一个计算问题的过程,5,计算机科学体系与算法的地位,可计算否,能行可计算否,算法设计与分析,用计算机语言实现算法,解决一个计算问题的过程,6,计算机科学体系与算法的地位,可计算否,能行可计算否,算法设计与分析,用计算机语言实现算法,解决一个计算问题的过程,7,算法概述 递归与
3、分制策略 动态规划 贪心算法 回溯算法 分支界限算法,课程内容,8,40学时（授课32、上机8） 2.5学分 平时成绩：20% 考试：80%,平时成绩和考试,9,算法的概念 算法分析 算法的复杂性概念 算法渐近复杂性的数学表述,第1章 算法概述,10,算法的概念,11,算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,算法,12,程序是算法用某种程序设
4、计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,程序(Program),13,确定性 算法的每一种运算必须有确切的定义,即每一种运算所执行的动作必须是相当清楚的,无二义性的 可实现性 算法中有待实现的运算都是相当基本的,每种运算至少在原理上可以（由人用纸和笔）在有限的时间内完成 输入 一个算法有一个或多个输入,这些输入是在算法开始之前给出的量,这些输入取自特定的对象集合 输出 一个算法产生一个或多个输
5、出,这些输出是与输入具有某种特定关系的量 有穷性 一个算法总是在执行了有穷步骤运算之后中止,算法的五个重要特性,14,问题的求解过程,理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,分析算法,设计程序,证明正确性,15,设Input和Output是两个集合。 一个问题是一个关系RInputOutput， Input称为问题R的输入集合， Input的每个元素称为R的一个输入； Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。,问题的定义,16,注意 问题定义了输入和输出的关系 例. SORT问题定义如下： 输入集合 Input= | ai是整数
6、输出集合 Output= | bi是整数, b1b2bn 问题 SORT=(，)| Input, Output, a1, , an=b1, , bn,问题的定义,17,问题R的一个实例是一个二元组 注意 一个算法面向一个问题，而不是仅求解一个问题的一个或几个实例。,问题实例,18,插入排序（抓扑克牌） A1 , n = 5, 2, 4, 6, 1, 3 A1 , n = 5 A1 , n = 2, 5 A1 , n = 2, 4, 5 A1 , n = 2, 4, 5, 6 A1 , n = 1, 2, 4, 5, 6 A1 , n = 1, 2, 3, 4, 5, 6,算法示例,19,算法示
7、例,Insertion-sort(A) Input: A1,.,n=n 个数 Output:A1,.,n=n 个 sorted 数 1. for j=2 to n do 2. keyAj; 3. ij-1; 4. while i0 and Aikey do 5. Ai+1Ai; 6. ii-1; 7. Ai+1key;,20,算法分析,21,定义：一个算法是正确的，如果它对于每一个输入都最终停止,而且产生正确的输出 不正确算法 不停止(在某个输入上) 对所有输入都停止，但对某个输入产生不正确的结果 近似算法 对所有输入都停止 产生近似正确的解或产生不多的不正确解 正确性证明 证明算法对所有输入
8、都停止 证明对每个输入都产生正确结果 调试程序程序正确性证明 “程序调试只能证明程序有错误，不能证明程序无错误”,算法正确性分析,22,只需证明循环不变性： 在每次for循环开始前，子数组A1j-1恰好是原始数组中A1j-1各元素排好序的形式 证明 初始化：j = 2 归 纳：A1j-1排好序， Aj正确插入 终 止：算法终止时A1n 排好序,算法正确性证明,Insertion-sort(A) Input: A1,.,n=n 个数 Output:A1,.,n=n 个 sorted 数 1. for j=2 to n do 2. keyAj; 3. ij-1; 4. while i0 and A
9、ikey do 5. Ai+1Ai; 6. ii-1; 7. Ai+1key;,23,目的 预测算法对不同输入所需资源量 复杂性测度 时间，空间， I/O 等, 是输入大小的函数 用途 为求解一个问题选择最佳算法、最佳设备 需要的数学基础 离散数学，组合数学，概率论，代数等 需要的数学能力 建立算法复杂性的数学模型 数学模型化简,算法复杂性分析,24,算法的复杂性是算法效率的度量,是评价效法效率的重要依据 一个算法复杂性的高低体现在运行该算法所需的计算机资源的多少上 计算机的资源,主要体现在时间和空间(存储器)资源上。因而,算法的复杂性分为时间复杂性和空间复杂性。本课程主要对算法的时间复杂性进
10、行分析。 关于算法的复杂性,有两个问题需要搞清楚 用怎样的一个量来表达算法的复杂性 对一个具体的算法,怎样计算它的复杂性,算法的复杂性,25,定义 (输入的大小) 设Input是问题R的输入集合，R的输入大小是一个函数。F：InputN，N是正整数集合。 例： 排序问题的输入大小=数组的长度 矩阵问题的输入大小=矩阵的行数/列数 图论问题的输入大小=图的边数/结点数 定义（时间复杂性） 一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的原子操作或“步”数 时间复杂性是输入大小的函数 我们假设每一步的执行需要常数时间，实际上每步需要的时间量可能不同。 定义（空间复杂性） 一个算法对特定
11、输入的空间复杂性是该算法对该输入产生结果所需要的存储空间大小。,算法的复杂性,26,以插入排序算法为例 相同长度的数组 运行时间不一定相同 分析三种情况下的时间复杂性 （1）最好 （2）最坏 （3）平均 定义（空间复杂性） 一个算法对特定输入的空间复杂性是该算法对该输入产生结果所需要的存储空间大小。,算法的复杂性,27,算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。,算法的复杂性,28,（1）最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n （2）最好情况下的时间复杂性 Tmi
12、n(n) = min T(I) | size(I)=n （3）平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。,算法的时间复杂性,29,插入排序的时间复杂性（最坏）,Insertion-sort(A) 1. for j=2 to n do cost times 2. keyAj; - c1 n-1 3. ij-1; - c2 n-1 4. while i0 and Aikey do- c3 5. Ai+1Ai; - c4 6. ii-1; - c5 7. Ai+1key; - c6 n-1,30,插入排序的时间复杂性（最好）,Insert
13、ion-sort(A) 1. for j=2 to n do cost times 2. keyAj; - c1 n-1 3. ij-1; - c2 n-1 4. while i0 and Aikey do- c3 n-1 5. Ai+1Ai; - c4 0 6. ii-1; - c5 0 7. Ai+1key; - c6 n-1,31,插入排序的时间复杂性,32,T(n) , as n ; (T(n) - t(n) )/ T(n) 0 ，as n; t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简
14、单。,算法的渐近复杂性,33,对于正值函数f(n) 0和g(n) 0，如果存在正常数c和n0使得对所有n n0有：f(n) cg(n) ，则称f(n) 是g(n)的低阶函数或g(n)是f(n)的渐近上界，记为f(n)=O(g(n),渐近分析的记号 渐进上界 O,34,对于正值函数f(n) 和g(n) ，如果存在正常数c和n0使得对所有n n0有：f(n) cg(n) ，则称f(n)是g(n)的高阶函数或g(n)是f(n)的渐近下界，记为 f(n)=(g(n),渐近分析的记号 渐进下界 ,35,对于正值函数f(n) 和g(n) ，如果存在正常数c1，c2和n0使得对所有n n0有： c1g(n) f(n) c2g(n) ，则称f(n
