算法分析第一章导论

1 主讲教师 孙成敏suncm 2015年3月 2015年6月 计算机算法设计与分析 2 课程设置 类别 专业必修课学分 3学分理论学时 48习题课学时 8开课周数 1 14周 3 基本内容 导引 第一 二章 基本的算法设计策略分治法 第四章 贪心方法 第五章 动态规划 第六章 回溯法 第八章 分支 限界法 第九章 基本算法分析方法NP 难度和NP 完全问题 第十章 4 学习目标 掌握基本的算法设计方法掌握进行算法分析的基本方法 时间 空间复杂度分析 灵活运用基本的算法设计方法 解决实际问题 5 参考书目 计算机算法设计与分析王晓东电子工业计算机算法设计与分析苏德富电子工业 8 问 交给你的问题 解决方法想出来了吗 答 我找不到一个有效的方法来解决它 因为这样的方法是不存在的 要证明一个问题不存在有效的方法 往往比寻找一种有效方法更难 9 问 交给你的问题 解决方法想出来了吗 答 我找到了一方法来解决它 理论上可实现的 但是以我们目前的力量实现它是不可能的 方法消耗的资源太大了 问题解决的好吗 10 现实世界的两个问题 问题能解决吗 可计算性 问题解决的好吗 计算复杂性 11 可计算性研究的范畴 计算机虽然神通广大 还是在人的控制下工作 计算机并非什么都能做 有的事情理论上它根本做不了 讨论哪些事计算机能做 哪些事计算机做不了 属于可计算性理论研究的范畴 12 一个满足可计算性的问题 26个英文字母全排列 它的排列数为26 4 1026以每年365天计算 共有365 24 3600 3 1536 107秒 以每秒能完成107个排列的超高速电子计算机来做这项工作 需要4 1026 3 1536 107 107 1 2 1012年 千亿年 13 有一些问题虽然在理论上能够由计算机解决 但因其算法占用资源太多而无法实际完成 因此需要选择其他算法或改进算法 要知道算法的优劣好坏 就要对算法需要多少计算时间和存储空间做定量的分析 算法分析研究的范畴 迄今为止 已有20 左右的计算机科学家因其在计算复杂性方面的研究工作而获得图灵奖 14 本课程的计算机 本课程指的计算机是和图灵机计算能力等价的 冯诺伊曼体系结构计算机 即确定性图灵机 量子计算机是非确定性图灵机 其算法和计算复杂性完全不同 15 几个典型的非数值计算问题 巡回推销员问题n皇后问题背包问题 16 巡回推销员问题 动态规划 设有n个城市 已知任意两城市间之距离 现有一推销员想从某一城市出发巡回经过每一城市 且每城市只经过一次 最后又回到出发点 问如何找一条最短路径 试一试求出最短路径 17 n皇后问题 回溯法 这是高斯1850年提出的一个著名问题 国际象棋中的 皇后 在横向 竖向和斜向都能走步和吃子 问在n n格的棋盘上如何能摆上n个皇后而使她们都不能互相吃 当n很大时 问题很难 对于n 8 现已知此问题共有92种解 但只有12种是独立的 其余的都可以由这12种利用对称性或旋转而得到 设n 4 试一试 18 背包问题 有一旅行者要从3种物品中选取不超过50公斤重的行李随身携带 要求总价值最大 物品1重10千克 价值60元 物品2重20千克 价值100元 物品3重30千克 价值120元 动态规划 物品不可分割的前提下 求总价值最大 贪心算法 物品可以分割的前提下 求总价值最大 19 发展历史 D Knuth TheArtofComputerProgramming A V Aho J Hopcroft J Ullman TheDesignandAnalysisofcomputerAlgothms ThomasH Cormen CharlesE Leiserson RonaldL Rivest IntroductiontoAlgorithms 20 第二章导引与基本数据结构 2 1算法2 2分析算法及数学基础2 3用SPARKS语言写算法2 4基本数据结构 略 21 2 1算法 什么是算法算法的重要特性计算过程与算法的区别问题的求解过程算法学习的基本内容 22 什么是算法 算法是解决一确定类问题的任意一种特殊的方法 数值计算方法非数值计算方法算法的非形式描述 算法就是一组有穷的规则 它规定了解决某一特定类型问题的一系列运算 求解数值问题 插值计算 数值积分等 求解非数值问题 主要进行判断比较 23 算法的五个重要特性确定性 每一种运算必须要有确切的定义 无二义性 能行性 运算都是基本运算 原则上能在有限时间内完成 输入 有0个或多个输入 输出 一个或多个输出 有穷性 在执行了有穷步运算后终止 仅仅有穷还不够 还要在现代计算机上有效才行 24 计算过程与算法的区别 计算过程可以不满足算法的性质 5 有穷性 例如操作系统 当没有任务时 操作系统并不终止 而是处于等待状态 直到有新的任务启动 因而不是一个算法 程序 算法 数据结构 ByWirth 25 问题的求解过程 证明正确性 分析算法 理解问题 精确解或近似解算法设计策略选择数据结构 设计算法 设计程序 26 算法学习的基本内容如何设计算法如何表示算法如何确认算法如何分析算法如何测试程序 27 如何设计算法 面对具体问题 运用一些基本设计策略 规划算法 被实践证明是有用的计算机科学 运筹学 电器工程等领域设计出很多精致有效的好算法掌握这些策略 设计出更多的好算法 28 如何表示算法 设计的算法要用恰当的方式表示出来采用结构程序设计的方式SPARKS程序设计语言 简单明了 29 如何确认算法 算法确认 algorithmvalidation 证明该算法对所有可能的合法输入 都能给出正确答案算法确认的目的 确保该算法能正确无误地工作穷举法推理 数学归纳法 反证法构造性证明测试 30 如何分析算法 分析执行一个算法时 占用CPU时间完成运算 占用存储器的存储空间 存放程序和数据 即对一个算法需要多少计算时间和存储空间 做定量分析 31 测试程序 调试 调试只能指出有错误 而不能指出它们不存在错误 源于程序正确性的证明还没有取得突破性进展 时空分布图用各种给定数据执行调试后的程序测定计算时间和空间印证之前的分析是否正确指出实现最优化的有效逻辑位置 32 第二章导引 2 1算法2 2分析算法及数学基础2 3用SPARKS语言写算法2 4基本数据结构 33 2 2分析算法 算法分析目的算法分析的准备工作计算时间的渐进表示一些证明方法作时空性能分布图 34 算法分析的目的 算法分析 analysisofalgorithms 是对一个算法需要多少计算时间和存储空间作定量的分析 确定算法在什么样的环境下能够有效地运行 分析在最好 最坏和平均情况下的执行情况 对同一问题不同算法的有效性作出比较 35 算法运行假定的计算机类型 要求独立于具体的软硬件环境单纯分析算法 假定使用一台通用计算机顺序处理每条指令 存储容量足够大 存取时间恒定 第1次课程 36 第二章作业证明 n2 O n3 证明 2n2 11n 10 O n2 证明 O的以下两个性质成立 其中c是一个正常数 O f n O g n O f n g n O cf n O f n 证明 n3 O n2 37 判断以下命题是否成立 若成立 证明之 不成立 举反例 5 如果g n f n 则 f n g n f n 6 cf n f n 其中c是一个正常数 7 f n f n 8 f n g n min f n g n 9 f n g n max f n g n 10 f n g n f n g n 38 算法分析过程 确定算法所涉及的运算 分析算法语句的执行次数 分析算法的执行时间的渐进表示 确定出能反映算法在各种情况下工作的数据集 作时空性能分布图 事前分析 准备工作 事后测试 全面分析的两个阶段 39 准备工作 一 首先确定使用哪些运算以及执行这些运算所用的时间 基本运算由一些更基本的任意长序列的运算所组成的复杂运算 40 基本运算 时间囿界于常数的运算加 减 乘 除整数算术运算浮点算术 字符比较 对变量赋值 过程调用等每种运算所用时间虽然不同 但都只花费一个固定量的时间 41 复杂运算 由一些更基本的任意长序列的运算组成如 两个字符串的比较运算一系列字符比较指令一个字符的比较时间 囿界于常数字符串比较的时间总量则取决于字符串的长度 42 准备工作 二 其次是要确定出能反映算法在各种情况下工作的数据集 编造出能产生最好 最坏和有代表性情况的数据配置通过使用这些数据来运行算法 以更了解算法的性能 算法分析最重要和最富于创造性的工作 43 全面分析算法的两个阶段 事前分析 aprioranalysis 确定每条语句的执行次数 求出该算法的一个时间限界函数 一些关于参数的函数 事后测试 aposteriortesting 收集此算法的实际执行时间和占用空间的统计资料 44 算法的执行时间 同一条语句在一个算法中的执行次数 frequencycount 称为频率计数语句的时间总量 频率计数 执行一次该语句所需要的时间算法的执行时间就是构成算法的所有语句的执行时间总量之和 由算法就可直接确定 与所用的机器无关 且独立于程序设计语言 依赖机器 程序设计语言 编译程序 45 例 计算语句x x y在下面三个程序段中的频率计数 beginx x yendFC 1 beginfori 1tondox x yendFC n beginfori 1tondoforj 1tondox x yendFC n2 语句的数量级是指执行它的频率计数之和算法的数量级是指算法的所有语句的执行频率之和 确定一个算法的数量级十分重要 因为它在本质上反映了算法所需的计算时间 46 计算时间的基本特性 描述算法数量级的多项表达式最高次项最高次项的系数最高次项的次数 准确分析出算法数量级的多项式表达式是很困难的 因此我们对事前分析的计算时间进行渐进表示 47 时间复杂性的形式化定义 算法的时间复杂性表示为T n 其中n是问题的规模 最坏情况下 Tmax n max T I size I n 最好情况下 Tmin n min T I size I n 平均情况下 Tavg n P I T I 其中I是问题规模为n的实例 p I 是实例I出现的概率 size I n 48 计算时间的渐进表示 定义2 1 f n O g n 定义2 2 f n g n 定义2 3 f n g n 定理2 1 49 f n 表示算法的计算时间n表示问题的规模输入或输出量 两者之和 其中之一的某种测度 g n 是在事前分析中确定的某个形式简单的函数 变量和函数的含义 f n 与机器和语言有关 而g n 是独立于机器和语言的 50 定义2 1 如果存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记做f n O g n 当n充分大时 f n 有上界 一个常数倍的g n 是f n 的一个上界 f n 的数量级就是g n f n 的阶不高于g n 的阶 在确定f n 的数量级时 总是试图求出最小的g n 有关证明中 找出c和n0是关键 51 例子判断f n O g n f n 3n g n 4nf n n 1024 g n 1025nf n 2n2 11n 10 g n n2f n n2 g n n3反例 f n n3 g n 5n2 52 O性质 对于非负的f n 和g n 根据定义2 1 有如下性质 1 O f n O g n O max f n g n 2 O f n O g n O f n g n 3 O f n O g n O f n g n 4 如果g n O f n 则O f n O g n O f n 5 O cf n O f n 其中c是一个正的常数 6 f n O f n 53 定理2 1 若A n amnm a1n a0是一个m次多项式 则A n O nm 证明 取n0 1 当n n0时由A n 的定义和不等式关系 A B A B 有 A n amnm a1n a0 am nm a1 n a0 am am 1 n a0 nm nm am am 1 a0 nm取c am am 1 a0 有 A n cnm即 A n O nm 定理得证 54 定理2 1表明 变量n的最高阶数为m的任一多项式 与nm同阶 因此一个计算时间为m阶多项式的算法 其时间都可以用O nm 来表示 若一个算法有数量级为c1nm1 c2nm2 cknmk的k个语句 则算法的数量级及计算时间就是c1nm1 c2nm2 cknmk O nm 其中m max mi 1 i k 若A n amnm a1n a0是一个m次多项式 则A n O nm 55 从计算时间上对算法分类 多项式时间算法 polynomialtimealgorithm 用多项式来对其计算时间限界的算法O 1 O logn O n O nlogn O n2 O n3 指数时间算法 exponentialtimealgorithm 计算时间用指数函数限界的算法O 2n O n O nn 数量级对算法有效性的影响 56 不同时间复杂性函数的对比 57 小规模数据 58 中等规模数据 59 定义2 2如果存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记做f n g n 当n充分大时 f n 有下界 一个常数倍的g n 是f n 的一个下界 f n 的阶不低于g n 的阶 在确定f n 的下界时 总是试图求出最大的g n 有关证明中 找出c和n0是关键 60 性质 对于非负的f n 和g n 根据定义2 2 有如下性质 1 f n g n min f n g n 2 f n g n f n g n 3 f n g n f n g n 4 如果g n f n 则 f n g n f n 5 cf n f n 其中c是一个正的常数 6 f n f n 61 定义2 3如果存在两个正常数c1 c2和n0 对于所有的n n0 有c1 g n f n c2 g n 则记作 f n g n 一个算法的f n g n 意味着该算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的 第2次课程 62 渐近表示函数的若干性质 1 传递性f n g n g n h n f n h n f n O g n g n O h n f n O h n f n g n g n h n f n h n 2 反身性f n f n f n O f n f n f n 3 对称性f n g n g n f n 4 互对称性f n O g n g n f n 63 5 算术运算O f n O g n O max f n g n O f n O g n O f n g n O f n O g n O f n g n O cf n O f n f n O g n O f n O g n O g n 也有类似性质 证明方法类似 渐近表示函数的若干性质 64 规则O f n O g n O max f n g n 的证明 对于任意f1 n O f n 存在正常数c1和自然数n1 使得对所有n n1 有f1 n c1f n 类似地 对于任意g1 n O g n 存在正常数c2和自然数n2 使得对所有n n2 有g1 n c2g n 令c3 max c1 c2 n3 max n1 n2 h n max f n g n 则对所有的n n3 有f1 n g1 n c1f n c2g n c3f n c3g n c3 f n g n 2c3max f n g n 2c3h n O max f n g n 65 规则O f n O g n O f n g n 的证明 对于任意f1 n O f n 存在正常数c1和自然数n1 使得对所有n n1 有f1 n c1f n 类似地 对于任意g1 n O g n 存在正常数c2和自然数n2 使得对所有n n2 有g1 n c2g n 令c3 max c1 c2 n3 max n1 n2 h n f n g n 则对所有的n n3 有O f n O g n f1 n g1 n c1f n c2g n c3f n c3g n c3 f n g n c3h n O f n g n 66 规则O f n O g n O f n g n 的证明 对于任意f1 n O f n 存在正常数c1 1和自然数n1 使得对所有n n1 有f1 n c1f n 类似地 对于任意g1 n O g n 存在正常数c2 1和自然数n2 使得对所有n n2 有g1 n c2g n 令c3 c1 c2 n3 max n1 n2 h n f n g n 则对所有的n n3 有O f n O g n f1 n g1 n c1f n c2g n c3f n g n c3h n O f n g n 67 数学基础 1 常用的整数求和公式通式 68 算法渐近复杂性分析中常用函数 2 单调函数单调递增 m n f m f n 单调递减 m n f m f n 严格单调递增 m n f m f n 严格单调递减 m n f m f n 3 取整函数 x 不大于x的最大整数 2 5 2 2 2 x 不小于x的最小整数 2 5 3 2 2 69 取整函数的若干性质 x 1 x x x x 1 n 2 n 2 n 对于n 0 a b 0 有 n a b n ab n a b n ab a b a b 1 b a b a b 1 b f x x g x x 为单调递增函数 70 4 多项式函数p n a0 a1n a2n2 adnd ad 0 p n nd p n O nk p n 多项式有界 p n O 1 p n c 71 指数函数一些性质对于正整数m n和实数a 0 a0 1 a1 a a 1 1 a am n amn am n an m aman am n a 1 an为单调递增函数 a 1 nb o an 72 ex 1 x x 1 1 x ex 1 x x2 ex 1 x x2 asx 0 73 logn log2n lgn log10n lnn logen logkn logn k loglogn log logn fora 0 b 0 c 0 5 对数函数 74 75 x 1 forx 1 foranya 0 logbn O na 76 6 阶乘函数Stirling sapproximation 77 78 一些数学证明方法 直接证明 P Q间接证明 反证法举反例数学归纳法 初始归纳 i 1结论成立 归纳假设 若i n 1时成立 归纳证明 证明i n时成立 79 时空分布图 事后测试是在对算法进行设计 确认 事前分析和调试之后要做的工作 以确定程序所耗费的精确时间和空间 即作时空性能分布图 与所用计算机密切相关 以时间分布图为例 要求 时钟及其精确度操作系统的工作方式解决因时钟误差引起的噪声问题 推荐两种方法 增加输入规模增加执行次数时空分布图的做法用途比较同一问题的不同算法对算法改进前后进行比较 80 主要内容 2 1算法2 2分析算法及数学基础2 3用SPARKS语言写算法2 4基本数据结构 81 2 3用SPARKS语言写算法 SPARKS语言的基本数据类型 整型 integer 实型 real 布尔型 boolean 字符型 char SPARKS语言的变量命名规则 以字母开头 不允许使用特殊字符 不允许与保留字重复 赋值语句 变量 表达式 逻辑运算符 and or not关系运算符 布尔值 true false 数组 任意整数下界和上界的多维数组integerA l1 u1 ln un 例 integerx y charch 例 integerA 1 10 realB 3 6 1 4 82 SPARKS语言的条件语句 if条件thens1endifif条件thens1elses2endif case 条件1 s1 条件n sn else sn 1endcase SPARKS语言的case语句