算法设计：第一讲——2013.ppt

算法分析与复杂度计算 主讲教师 徐红艳 计算机系统中的任何软件 系统软件 应用软件 都是按照特定的算法来实现的 算法的好坏直接决定所实现软件性能的优劣 课程简介 设计软件时需要解决的问题 1 用什么方法设计软件 2 设计的算法需要什么样的资源 3 需要多少运行时间 4 需要多少存储空间 分析 算法设计与分析是计算机科学与技术的一个核心问题 课程简介 设计 参考教材 1 王晓东 算法设计与分析 第2版 清华大学出版社 2 潘彦 算法设计与分析基础 第2版 清华大学出版社 3 郑宗汉 算法设计与分析 清华大学出版社 课程简介 课程的侧重点 算法设计第三章 算法设计的基本工具和优化技术第四章 通用的算法设计基本策略第五章 复杂问题的算法设计策略第六章 采用不同策略解决相同问题 并进行效率分析 算法分析 对设计的算法进行时间和空间复杂度的分析 课程简介 第一章算法概述 人类使用计算机的目的 计算机作为工具 帮助人类求解问题 算法设计的重点 把人类找到的求解问题的方法 步骤以过程化 形式化和机械化的形式表现出来 以便让计算机执行 算法分析 是对一个算法需要多少计算时间和存储空间作定量的分析 复杂度计算 1 1用计算机求解问题与算法 1 1 1用计算机求解问题的步骤 人在解决问题时有很大的灵活性 对于同一个问题 不同的人有不同的经验 会采用不同的方法 如何用计算机解决一个现实中的问题呢 虽然有很多不同的方法 但基本步骤是相同的 问题分析数学模型建立算法设计与选择算法表示算法分析算法实现程序调试结果整理文档编制 用计算机解决一个现实中的问题步骤 1 1 1用计算机求解问题的步骤 问题分析 准确 完整地理解和描述问题是解决问题的第一步 数学模型建立 用计算机解决实际问题必须有合适的数学模型 算法设计与选择 算法设计是指设计求解某一特定类型问题的一系列步骤 并且这些步骤是可以通过计算机的基本操作来实现的 1 1 1用计算机求解问题的步骤 算法分析 对算法的某些特定输入 估算该算法所需的内存空间和运行时间 其次是为了建立衡量算法优劣的标准 用以比较同一类问题的不同算法 通常将时间和空间的增长率作为衡量的标准 1 1 1用计算机求解问题的步骤 算法表示 对于复杂的问题 确定算法后可以通过图形准确表示算法 算法的表示方式很多如 算法流程图 盒图 PAD图和伪码 类似于算法设计语言 等 算法实现 根据选用的程序设计语言 编写出计算机能够执行的程序 1 1 1用计算机求解问题的步骤 程序调试 算法测试的实质是对算法应完成任务的实验证实 同时确定算法的使用范围 测试方法一般有两种 白盒测试对算法的各个分支进行测试 黑盒测试检验对给定的输入是否有指定输出 1 1 1用计算机求解问题的步骤 结果整理文档编制 编制文档的目的是让人了解你编写的算法 在这些步骤中 算法设计是解决问题的核心 其次是针对设计的算法进行复杂度分析 1 1 1用计算机求解问题的步骤 1 1 2算法及其要素和特性 算法的定义 算法是求解某一特定问题的一组有穷规则的集合 算法的要素 操作 算术运算 关系比较 逻辑运算 数据传送 I O 赋值等 控制结构 顺序 选择 循环控制 也称迭代 数据结构 数据的逻辑结构及存储结构 1 1 2算法及其要素和特性 算法的基本性质 目的性 能完成赋予它的功能分步性 由一系列计算机可执行的步骤组成有序性 不可随意改变算法步骤的执行顺序有限性 算法所包含的步骤是有限的 操作性 算法总是对某些对象进行操作 使其状态改变 完成特定功能 算法的基本特征有穷性 一个算法在执行有穷步之后必须结束 而且要求运行这些步骤的时间是人们可以接受的 确定性 在任何条件下 算法都只有一条执行路径 可行性 算法中描述的操作都可以通过已经实现的基本操作运算有限次实现 输入 有零个或多个输入输出 有一个或多个输出 1 1 2算法及其要素和特性 1 1 3算法设计及基本方法 算法设计的概念 其任务是对各类具体问题设计良好的算法 算法设计应注意的问题正确性 Correctness 可读性 Readability 健壮性 Rubustness 高效率与低存储量需求 算法设计的基本方法结构化方法 自顶向下 逐步求精 自顶向下 是将复杂 大的问题划分为小问题 逐步求精 是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题 1 1 3算法设计及基本方法 面向对象方法对象 数据 对数据操作的代码实体面向对象算法设计方法的过程包括以下步骤 在给定的抽象层次上识别类和对象 识别这些对象和类的语义 识别类和对象之间的关系 实现类和对象 1 1 3算法设计及基本方法 本书采用的设计方法 结构化设计方法自顶向下模块化分解过程把一个较大的算法划分为若干子算法每一个模块可继续划分为更小的子模块直到用三种控制结构和具体操作表示算法 注 运用这种编程方法 考虑问题必须先进行整体分析 1 1 3算法设计及基本方法 模块划分的基本要求 简单性 独立性和完整性模块的功能尽可能地单一化 明确化模块间的联系及相互影响尽可能地小模块的规模应当足够小 以便于调试 1 1 3算法设计及基本方法 算法设计的基本方法抽象 包括算法的抽象和数据抽象 算法抽象是指算法的寻求 或开发 采用逐步求精 逐层分解的方法 数据抽象也指在算法抽象的过程中逐步完善数据结构和引入新的数据及确定关于数据的操作 枚举 枚举 一些真实数据归纳 归纳 出算法的细节 1 1 3算法设计及基本方法 1 2 1算法描述简介 算法是对解题过程的精确描述 算法 控制结构 原操作表示算法的语言主要有 自然语言流程图伪代码计算机算法设计语言 本书采用类C语言的伪代码描述 具体细节约定如下 三种基本控制结构的描述数据结构说明模块及模块间的接口方式的描述其它细节说明 1 2 2本书算法描述约定 1 2 3一个简单问题的求解过程 问题求解的步骤可以简化为三步问题分析 在对问题进行认真分析的基础上 确认问题的逻辑结构和问题的基本功能 并在数学 物理等问题领域相关知识的基础上建立数学模型 算法设计 找出解决问题的处理步骤算法分析 对数学模型的建立 数据结构的选择及算法设计工作的评价 总结 例 求二个正整数的最大公约数 问题分析 此题只需有小学知识 就可有以下建立以下的数学模型 数学模型 a b 0的整数 求c c能整除a b 且a c与b c互质 算法设计 通过 枚举尝试 逐个尝试 就可以 试出 a b有哪些是公约数 并将这些公约数 累乘 就能得到最大公约数 1 2 3一个简单问题的求解过程 算法描述如下 zdgys inta b c i input a b c 1 变量c是为累乘因数而设置的 for i 2 i aandi b i 枚举 可能的公约数while a i 0andb i 0 试 i是否为公约数 c c i a a i b b i print dismaximalcommondivisor c 算法效率分析 由于算法是盲目地尝试可能的因数 比较操作次数较多 所以算法的效率并不高 问题分析 建模 算法设计要点 算法分析 是解决问题的必然过程 1 2 3一个简单问题的求解过程 下面是算法设计时需要注意的一些问题 通过输入语句增加算法的通用性会忘掉 输出 或在模块间传递处理的数据结果易忽略细节造成 死循环 出现语序方面的错误 特别是双重循环中指令常有嵌套错误 1 2 3一个简单问题的求解过程 注意学习和总结 用大脑 运行 算法是学习算法很好的方法 解题时要学会择优 简单说择优要考虑四个方面 可读性 可修改性 时间效率和空间效率 1 2 3一个简单问题的求解过程 第二章算法分析基础 算法分析的重要性 1 百钱买百鸡问题问题叙述 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 问鸡翁 母 雏各几何 算法实现 1 及分析算法实现 2 及分析 算法分析的重要性 2 货郎担问题问题描述 某售货员要到若干个城市销售货物 已知各城市之间的距离 要求售货员选择出发的城市及旅行路线 使每个城市仅经过一次 最后回到原出发城市 而总路程最短 问题分析 算法实现 算法分析 算法分析的重要性 算法效率的衡量标准 算法的复杂度 包括算法的时间复杂度和空间复杂度 算法分析的任务 对设计出的每一个具体的算法 利用数学工具 讨论其复杂度 2 1 1算法分析的评价体系 人对算法的维护主要有编写 调试 改正和功能扩充等工作 这就需要在算法设计时注重算法的可读性 机器对算法的运行效率主要包括时间效率和空间效率 算法在完成功能的前题下最好是占用空间少而且执行时间短 算法实现时 要考虑算法在运行过程中与使用者进行交互的情况 这就要求 算法的交互部分要具有友好性和健壮性 总之 对算法的分析和评价 一般应考虑正确性 可维护性 可读性 运算量及占用存储空间等诸多因素 其中评价算法的三条主要标准是 1 算法实现所耗费的时间 2 算法实现所所耗费的存储空间 其中主要考虑辅助存储空间 3 算法应易于理解 易于编码 易于调试 2 1 1算法分析的评价体系 1 和算法执行时间相关的因素 1 问题中数据存储的数据结构2 算法采用的数学模型3 算法设计的策略4 问题的规模5 实现算法的程序设计语言6 编译算法产生的机器代码的质量7 计算机执行指令的速度 2 1 2算法的时间复杂性 假定 百钱买百鸡的问题中 其最内部的循环体每执行一次需要1 s时间 算法的输入规模和运行时间的阶 对n 220个数进行排序 选择排序需64天 合并排序需要20秒 通过上面问题的分析 可以知道 1 算法的执行时间随着问题规模的增大而增长 增长的速度随不同的算法而不同 2 没有一个方法能准确的计算出算法的执行时间 原因 算法的输入规模和运行时间的阶 算法的输入规模和运行时间的阶 算法的运行时间表示为一个与输入规模n相关的函数f n 反映算法的运行时间随着输入规模的增长而增长的情况 若将问题的输入规模设为n 则百钱买百鸡 算法1的时间花费估算 第4行 1第5行 1 2 n 1 第6行 n 1 2 n 1 2第7行 n 1 2 2 n 1 3第8行 14 n 1 3第9 10 11 12行 不超过4 n 1 3 算法的输入规模和运行时间的阶 则该算法的时间花费T1 n 算法的输入规模和运行时间的阶 算法的输入规模和运行时间的阶 随着n的增大 例如当n 100万时 算法的主要执行时间主要取决于算式中的第一项 而且随着n的增大 第一项的系数对算法的执行时间也变得不重要 于是 可把T1 n 改写为 这时 称的阶是 百钱买百鸡 算法2的时间花费估算 第4行 1第5 6行 各2个2 2 4第7行 1 2 n 5 1 第8行 n 5 1 2 n 5 1 n 3 1 第9行 3 n 5 1 n 3 1 第10行 10 n 5 1 n 3 1 第11 12 13 14行 不超过4 n 5 1 n 3 1 算法的输入规模和运行时间的阶 算法的输入规模和运行时间的阶 这时 称的阶是 算法的输入规模和运行时间的阶 把T1 n 和T2 n 进行比较 有 当n很大时 c1 c2的作用很小 通常有两种衡量算法效率的方法 1 事后统计法 有缺点 较少使用 2 事前分析估算法算法的时间效率是问题规模的函数 假如 随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 则可记作 T n f n 算法效率的衡量方法 定义2 1 设算法的执行时间为T n 如果存在T n 使 称T n 为算法的渐进时间复杂度 在算法分析中用渐进时间复杂性来衡量一个算法的时间复杂性 在百钱买百鸡问题中 1 算法1的时间性为T1 n 它的阶是n3 2 算法2的时间性为T2 n 它的阶是n2 表示时间复杂性的阶为 表1 不同时间复杂性下不同输入规模的运行时间 时间复杂度 假定在计算机C1和C2上运行这些算法 1 C2机的速度是C1机的10倍 2 这些算法在C1机上的运行时间为T 可处理的输入规模是n1 3 在C2机上运行同样时间 可处理的规模扩大为n2 表2 计算机速度提高 不同算法复杂性求解规模的扩大 假定A1 A2 A3 A6是求解同一个问题的6个算法 它们的时间复杂度分别为 时间复杂度 前4种时间复杂性 与输入规模n的一个确定的幂同阶 计算机运算速度的提高 可以使阶梯规模以一个常数因子的倍数增加 通常把这类算法称为多项式时间算法 后2种时间复杂性 称为指数时间算法 时间复杂度 运行时间的上界 O记号 在百钱买百鸡问题中 1 算法1执行基本操作的步骤至多为C1 n3 当n的规模增大时 常数C1对运行时间的影响不大 则算法1的运行时间的上界写成 O n3 2 同理 算法2的的运行时间的上界写成 O n2 运行时间的上界 O记号 在一般情况下 当输入规模大于或等于某个阈值n0时 算法运行时间的上界是某个正常数C的g n 倍 就称算法的运行时间至多是O g n O记号的定义如下 定义 令N为自然数集合 R 为正实数集合 函数f N R 函数g N R 若存在自然数n0和正常数c 使得对所有的n n0 都有f n cg n 就称函数f n 的阶至多是O g n 运行时间的上界 O记号 因此 如果存在则 即意味着 f n O g n 这个定义表明 f n 的增长至多象g n 的增长那样快 这时称O g n 是f n 的上界 举例 运行时间的下界 记号 在百钱买百鸡问题中 1 第11 12 13 14行 仅在条件成立时才执行 其执行次数未知 2 假定条件都不成立 这些语句一次也没有执行 该算法的执行时间至少为 算法执行时间计算 运行时间的下界 记号 在一般情况下 当输入规模大于或等于某个阈值n0时 算法运行时间的下界是某个正常数C的g n 倍 就称算法的运行时间至少是 g n 记号的定义如下 定义 令N为自然数集合 R 为正实数集合 函数f N R 函数g N R 若存在自然数n0和正常数c 使得对所有的n n0 都有f n cg n 就称函数f n 的阶至少是 g n 运行时间的下界 记号 因此 如果存在则 即意味着 f n g n 这个定义表明 f n 的增长至少象g n 的增长那样快 这时称 g n 是f n 的下界 举