计算机算法设计与分析第1章算法概述

1 算法分析与设计 手机 Mail easyguan 主讲教师 管涛 2 课程安排 理论课 1 10周 40学时周二 5 6 周五 1 2 上机 18学时期末考试 闭卷笔试 第11周上课点名三次不到者取消考试资格 迟到或作业缺交 一次扣10分 平时成绩 3 教学目的和要求 本课程是计算机类专业的专业基础课程 通过课程学习和上机实践 对计算机常用算法有一个较全面的了解 掌握通用算法的一般设计方法 学会对算法的时间 空间复杂度分析 掌握提高算法效率的方法和途径 4 学习算法的重要性 一 从理论和实践的角度理解 计算机科学的基石 掌握标准算法 二 从算法对于程序的重要性来讲 皮之不存 毛将附焉 三 从对同学们的能力培养看 开发分析问题的能力 5 算法分析与设计课程与数据结构课程 一 数据结构关心的对象各种数据结构的作用和效率 具体的问题 二 算法设计与分析关心的对象算法设计技术的适用性和效率 一般性方法 6 授课内容 第1章算法概述第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法 7 9章属研究生学习内容 可自学了解 7 第1章算法概述 学习要点 一 理解算法的概念 以及问题求解的过程 二 掌握算法的几种描述方式 三 理解算法的计算复杂性概念 四 掌握算法渐近复杂性的数学表述 8 什么是算法 我们来编写一个烧开水的算法 输入自来水循环 反复 加热直到水开输出开水 9 一 算法 Algorithm 算法概念 通俗地讲 算法是指解决问题的一种方法或一个过程 严格地讲 算法是由若干条指令组成的有穷序列 图1 1算法的概念图 10 一 算法的性质 1 算法具有某些特性 如下几条 1 输入 有零个或多个外部提供的量作为算法的输入 2 输出 算法产生至少一个量作为输出 这些输出是和输入有某种特定关系的量 11 一 算法的性质 3 确定性 组成算法的每条指令是清晰 无歧义的 4 有限性 有穷性 算法中每条指令的执行次数是有限的 执行每条指令的时间也是有限的 12 一 算法的性质 5 可实现性 此性质是指算法中有待实现的运算都是相当基本的 每种运算至少在原理上能由人用纸和笔在有限的时间内完成 补充 13 一 算法性质 2 关于算法有几个要点 1 算法所处理的输入的值域必须严格定义 2 同样一种算法可以用几种不同的形式来描述 14 一 算法性质 3 同一个问题可以存在多种解决的算法 4 同一个问题的几种算法可能会基于完全不同的解题思路 而且解题速度也会有显著不同 15 二 问题求解过程 1 问题的陈述用科学规范的语言 对所求解的问题做准确的描述 2 建立数学模型通过对问题的分析 找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述 3 算法设计根据数学模型设计问题的计算机求解算法 16 二 问题求解过程 4 算法的正确性证明证明算法对一切合法输入均能在有限次计算后产生正确输出 5 算法的程序实现将算法正确地编写成机器语言程序 6 算法分析对执行该算法所消耗的计算机资源进行估算 17 三 如何设计算法 通过学习已被实践证明是有用的一些基本设计策略 如递归 回溯等 掌握一般的算法设计方法 学会设计高效的算法 18 四 如何确认算法 证明其正确性 证明算法对所有可能的输入都能算出正确的答案 这一工作称为算法确认 这一领域是当前许多计算机工作者集中研究的对象 还处于相当初期的阶段 在学习本课程中 我们仅对算法的正确性进行一般的非形式化讨论 以及对算法的程序实现进行测试验证 19 五 如何分析 评价 算法 分析算法包括定量的分析算法需要多少计算时间和存储空间 分析算法不仅可以预计算法能否有效得完成任务 而且可以知道算法在最坏 最好和平均情况下的运算时间 对解决同一问题的不同算法的优劣作出比较 20 二 算法的几种描述方式 1 计算两个整数的最大公约数问题的一个现代数学术语表述欧几里得算法基于的方法是重复应用下列等式 gcd m n gcd n mmodn 直到mmodn等于0 gcd 60 24 gcd 24 12 gcd 12 0 12注 gcd m 0 m mmodn表示m除以n之后的余数 称为模运算 21 2 算法的一个结构化的描述 计算gcd m n 的欧几里得算法 第一步 如果n 0 返回m的值作为结果 同时过程结束 否则 进入第二步 第二步 用n去除m 将余数赋给r 第三步 将n的值赋给m 将r的值赋给n 返回第一步 22 ALGORITHMEuclid m n 计算gcd m n 输入 非负整数m n 其中m n不同时为零 输出 m n的最大公约数whilen 0dor mmodnm nn rreturnm 3 算法的一个伪代码描述 23 4 算法的一个c 程序语言实现 intEuclid intm intn 计算gcd m n 输入 非负整数m n 其中m n不同时为零 输出 m n的最大公约数 intr 0 if m n 0 return0 m n不符合输入规范时返回0while n 0 r mmodn m n n r returnm 24 其他方法 程序流程图等 不再一一列举 25 三 算法复杂性分析 算法复杂性是算法效率的度量 是评价算法优劣的重要依据 算法复杂性的高低体现在运行算法所需要的计算机资源 即时间和空间 存储器 资源的多少上 算法的时间复杂性T n 空间复杂性S n 其中n是问题的规模 输入大小 26 三 算法复杂性分析 本课程主要对算法的时间复杂性进行分析 关于算法的复杂性 有两个问题要弄清楚 1 用怎样的一个量 指标 来表达一个算法的复杂性 2 对于一个算法 怎样具体计算它的复杂性 27 1 算法的三种时间复杂性 算法的最坏 最好和平均时间复杂性 1 最坏情况下的时间复杂性Tmax n max T I size I n 2 最好情况下的时间复杂性Tmin n min T I size I n 其中size I n表示I是规模为n的实例 28 1 算法的三种时间复杂性 3 平均情况下的时间复杂性Tavg n 其中p I 是实例I出现的概率 29 2 算法的时间复杂性计算 例 顺序查找算法的时间复杂度计算 已知不重复 从小到大排列的m个整数的数组A 1 m m 2K K为正整数 对于给定的整数c 要求找到一个下标i 使得A i c 找不到返回0 A 1 A m A i c 30 分析 问题的规模为m设元运算执行时间 赋值a 判断t 加法s设c在A中查找成功 31 2 算法的时间复杂性计算 intsearch intA intm intc inti 1 awhile A i ca 32 最好情况 比较次数为1Tmin m 2a 2t 时间复杂度函数最坏情况 比较次数为mTmax m m 1 a 2m 1 t m 1 s平均情况 假定所有数组元素是不同的 并且每个元素被查找的概率是相同的 则平均比较次数为 m 1 2Tavg m 0 5 m 3 a 0 5 2m 3 t 0 5 m 1 s 2 算法的时间复杂性计算 33 3 算法的改进 上面例子中顺序查找算法的改进有 进行二分 折半 查找 即反复把供查找的数组分成两半 然后在其中一半继续查找 A 1 A m A mid A mid c A mid c 34 3 算法的改进 intsearch Bin intA intc intm intlow 1 high m mid 0 found 0 while found 0 35 3 算法的改进 在最坏情况下 查找成功时最多只需检测A 1 m 中的 logm 1个分量 而改进前最坏情况下需要比较m个分量 如 c 5 A 1 11 1 2 3 11 对于查找算法 减少比较次数可以最有效地降低算法时间复杂度 算法改进的目的就是为了提高效率 注 本书中出现的logn相当于log2n 36 4 时间复杂性的计量 算法的时间复杂性计量是算法的运算时间 但对于同一类问题 采用算法的基本运算次数作为算法的运算时间 汉诺塔 的基本运算是圆盘的移动次数 查找 排序算法 元素的比较次数 矩阵相乘 两个数的相乘 树的搜索 节点的访问 图的算法 节点和边的访问 37 四 算法的渐近复杂性 随着要求用计算机解决的问题越来越复杂 规模越来越大 对这类问题的求解算法做复杂性分析具有特别重要的意义 因此 对于规模充分大 结构又十分复杂的算法 人们提出了如何简化其复杂性分析 及求解其复杂性函数f n 的上界和下界的问题 38 渐近复杂性的数学表述 用形式简单的函数代替形式复杂的函数 T n asn 这里 是指充分大 T n t n T n 0 asn t n 是T n 的渐近性态 为算法的渐近复杂性 39 渐近复杂性的数学表述 T n t n T n 0 asn 在数学上 t n 是T n 的渐近表达式 是T n 略去低阶项留下的主项 它比T n 简单 例如 T n 3n2 4nlogn 7 t n 3n2T n 4nlogn 7n t n 4nlogn因此 只要考察当问题规模充分大时 算法复杂性在渐进意义下的阶 就可以判定出哪一个算法的效率高 40 为此 我们引入以下渐进意义下的记号 O o 41 1 渐近上界记号O 在下面的讨论中 对所有n 时间复杂性函数f n 0 g n 0 g n 也称为f n 的阶函数 渐近上界记号O 给出函数f的一个上限O g n f n 存在正常数c和n0使得对所有n n0有 0 f n cg n 42 1 渐近上界记号O 例 例1 线性函数 考察f n 3n 2 当n 2时 3n 2 3n n 4n 所以f n O n f n 是一个线性变化的函数 类似地 100n 6 O n 特别地 当f n 是一个常数c时 如f n 9 可以记为f n O 1 43 1 渐近上界记号O 例 例2 平方函数 考察f n2 10n2 4n 2 当n 2时 10n2 4n 2 5时 10n2 5n 4时 n2 2n 44 2 渐近下界记号 渐近下界记号 给出函数f的一个下限 g n f n 存在正常数c和n0使得对所有n n0有 0 cg n f n 45 2 渐近下界记号 例 例 对于所有n 有以下推导 3n 2 2n 3n 2 n 100n 6 100n 100n 6 n 10n2 4n 2 10n2 10n2 4n 2 n2 6 2n n2 6 2n 6 2n n2 2n 46 3 非紧上界记号o和非紧下界记号 非紧上界记号oo g n f n 对于任何正常数c 0 存在正数和n0 0使得对所有n n0有 0 f n cg n 等价于f n g n 0 asn 47 3 非紧上界记号o和非紧下界记号 非紧下界记号 g n f n 对于任何正常数c 0 存在正数和n0 0使得对所有n n0有 0 cg n f n 等价于f n g n asn f n g n g n o f n 48 3 非紧上界记号o和非紧下界记号 例 例1 3n 2 o n2 例2 10n2 4n 2 n 49 4 紧渐近界记号 g n f n 存在正常数c1 c2和n0使得对所有n n0有 c1g n f n c2g n 记号 适用于同一个函数g既可以作为函数f的上限也可以作为f的下限的情形 定理1 g n O g n g n 50 4 紧渐近界记号 例 例 对于所有n 有 3n 2 n 100n 6 n 10n2 4n 2 n2 6 2n n2 2n 51 O f n O g n f n 的阶不高于g n 的阶 f n g n f n 的阶不低于g n 的阶 f n g n f n 与g n 同阶 课后习题1 6 52 O的运算规则 以下设f n g n 是定义在正数集上的正函数 1 O f O g O max f g 2 O f O g O f g 3 O f O g O fg 4 如果f n O g n 则O f O g O g 5 O cf n O f n 其中c是一个正的常数 6 f O f 53 5 算法分析中常见的复杂性函数 课后习题1 3 54 1 小规模数据 图1 2时间函数的增长率 55 2 中等规模数据 图1 3时间函数的增长率 56 五 算法分析方法 一 算法分析的基本法则 非递归算法 1 for while循环循环体内计算时间 循环次数 2 嵌套循环循环体内计算时间 所有循环次数 57 一 算法分析的基本法则 非递归算法 3 顺序语句各语句计算时间相加 4 if else语句if语句计算时间和else语句计算时间的较大者 58 二 递归算法复杂性分析 建立算法的基本操作执行次数的递推关系式 然后确定它的增长次数 intfactorial intn if n 0 return1 returnn factorial n 1 59 本章小结 算