1-算法与复杂性分析.ppt

计算机算法设计与分析算法与复杂性分析 姜大志汕头大学计算机系 算法 Algorithm 算法是指解决问题的一种方法或一个过程 算法是若干指令的有穷序列 满足性质 1 输入 有外部提供的量作为算法的输入 2 输出 算法产生至少一个量作为输出 3 确定性 组成算法的每条指令是清晰 无歧义的 4 有限性 有穷性 算法中每条指令的执行次数是有限的 执行每条指令的时间也是有限的 5 可行性 算法中执行的任何计算步都是可以被分解为基本的可执行的操作步 即每个计算步都可以在有限时间内完成 也称之为有效性 2 2020 1 21 程序 Program 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的性质 4 例如操作系统 是一个在无限循环中执行的程序 因而不是一个算法 操作系统的各种任务可看成是单独的问题 每一个问题由操作系统中的一个子程序通过特定的算法来实现 该子程序得到输出结果后便终止 2020 1 21 3 问题求解 ProblemSolving 理解问题 精确解或近似解选择数据结构算法设计策略 设计算法 2020 1 21 4 构建模型 模型的构建是理解问题的结果 模型 是对实体的特征及变化规律的一种表示或抽象 即是把对象实体通过适当的过滤 用适当的表现规则描绘出的简洁的模仿品 2020 1 21 5 模型的分类 1 实体模型1 模拟模型2 事物模型 2 符号模型1 数学模型2 结构模型3 模仿模型4 科学符号5 描述模型 理解问题和模型构建是问题求解的关键 关于均值2 3的猜想 在这个游戏中 要求所有参与者在不知道其他人选择的情况下 每人给出一个0到100之间的数字 所给出的数字最接近平均值2 3的那个人将会是获胜者 2020 1 21 6 你将如何获胜 模型的构建1 按照理性人的假设 参与者们应该会先排除不可能的数字 例如超过67的数字就不可能 因为当大家都选100时 平均值的三分之二才不过66 这样一来 每个人的选择又变成了在0到66之间选一个数 此时大于44的数字又变得没有意义了 接下来又是一个类似的循环 直到最后 所有理性人的选择应该都为0 但是我相信在座并不是所有参与者都会遵照理性人的思路来思考这个问题 我假设有三分之一的人是任意的给出一数字 那么这三分之一人的均值的三分之二应该接近33 另外三分之一的人我们假定是进行这理性推理 选择的均值为0 最后三分之一我们我们考虑到存在一群和我有一样思维模式的人 认为一部分人理性一部分人不理性 那么他会选择两者均值的2 3 所以他会取值11 在对这三种人的均值的猜想下求均值的2 3 得到我的猜想为10 2020 1 21 7 模型的构建2 首先采用二八定律进行人群的划分 假设80 的人会在0到100之间随机选择一个数 那么可得80 的均值的2 3为33 还有20 的人是极度理性的人 他们选择平均数将在33左右间选择 设定为28 38 这种人在28到38之间随机选择一个数 通过计算模拟后得出总体均值的2 3为31左右 程序见附件 2020 1 21 8 反思 一个模型到底有多重要 模型中最重要的组成部分是什么 你还能够构建哪些模型 2020 1 21 9 算法复杂性分析 算法复杂性 算法所需要的计算机资源算法的时间复杂性T n 算法的空间复杂性S n 其中n是问题的规模 输入大小 2020 1 21 10 算法的时间复杂性 1 最坏情况下的时间复杂性Tmax n max T I size I n 2 最好情况下的时间复杂性Tmin n min T I size I n 3 平均情况下的时间复杂性Tavg n 其中I是问题的规模为n的实例 p I 是实例I出现的概率 2020 1 21 11 算法渐近复杂性 T n asn T n t n T n 0 asn t n 是T n 的渐近性态 为算法的渐近复杂性 在数学上 t n 是T n 的渐近表达式 是T n 略去低阶项留下的主项 它比T n 简单 2020 1 21 12 渐近分析的记号 在下面的讨论中 对所有n f n 0 g n 0 1 渐近上界记号OO g n f n 存在正常数c和n0使得对所有n n0有 0 f n cg n 2 渐近下界记号 g n f n 存在正常数c和n0使得对所有n n0有 0 cg n f n 2020 1 21 13 3 非紧上界记号oo g n f n 对于任何正常数c 0 存在正数和n0 0使得对所有n n0有 0 f n 0 存在正数和n0 0使得对所有n n0有 0 cg n f n 等价于f n g n asn f n g n g n o f n 2020 1 21 14 5 紧渐近界记号 g n f n 存在正常数c1 c2和n0使得对所有n n0有 c1g n f n c2g n 定理1 g n O g n g n 2020 1 21 15 渐近分析记号在等式和不等式中的意义 f n g n 的确切意义是 f n g n 一般情况下 等式和不等式中的渐近记号 g n 表示 g n 中的某个函数 确切定义 有时可以直接从计算n趋于无穷时的极限得到一个紧渐近的界 基本上 当n趋于无穷时如果函数f n 和g n 之比趋于一个正常数 那么f n g n 2020 1 21 16 渐近分析记号的若干性质 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 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 2020 1 21 17 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 f n o g n g n f n 2020 1 21 18 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 g n O f n O f n O g n O f n 2020 1 21 19 规则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 c32max f n g n 2c3h n O max f n g n 2020 1 21 20 算法分析技术 评价一个算法的代价 主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少 算法复杂性 算法所需要的计算机资源算法的分析主要包含时间和空间两个方面 2020 1 21 21 算法的空间复杂性 根据算法执行过程中对存储空间的使用方式 可以把对算法空间代价分析分成两种 静态分析和动态分析 2020 1 21 22 静态分析 一个算法静态使用的存储空间 称为静态空间 静态分析的方法比较容易 只要求出算法中使用的所有变量的空间 再折合成多少空间存储单位即可 2020 1 21 23 动态分析 一个算法在执行过程中 必须以动态方式分配的存储空间是指在算法执行过程中才能分配的空间称为动态空间 2020 1 21 24 动态空间的确定主要由两种情况构成 1 函数的递归 2 执行动态分配函数 函数的递归调用 对于递归函数而言 由于每次调用需要分配不同的运行空间 所以递归函数的空间代价 不能简单地采用静态分析方法 2020 1 21 25 执行动态分配函数 一个函数 或过程 如果使用了malloc和free函数 malloc和free所开辟 释放的空间只能在算法执行过程中加以确定 这些空间属于动态空间 2020 1 21 26 执行分配函数的两种情况 没有使用free函数动态空间代价为O k k为使用malloc的次数 包括在循环和递归调用中动态执行的次数 2020 1 21 27 执行分配函数的两种情况 2020 1 21 28 使用free函数设free使用次数为j 令 0 pi i 1 j 为第i 1次使用free和 次使用free之间执行malloc的次数 用公式 i i 1 pi 1可以计算出在第i 1次使用free和第i次使用free i 1 j 之间使用的最大动态空间数 再定义j 如下 于是整个算法使用的动态空间代价为 算法分析中常见的复杂性函数 2020 1 21 29 算法时间效率的度量分析 2020 1 21 30 常见函数的增长率 小规模数据 2020 1 21 31 中等规模数据 2020 1 21 32 时间代价分析 c log2N n n Log2N n 2 n 3 2 n 3 n n 算法的执行时间绝大部分花在循环和递归上 2020 1 21 33 算法分析方法 2020 1 21 34 例 顺序搜索算法 templateintseqSearch Type a intn Typek for inti 0 i n i if a i k returni return 1 算法分析 2020 1 21 35 1 Tmax n max T I size I n O n 2 Tmin n min T I size I n O 1 3 在平均情况下 假设 a 搜索成功的概率为p 0 p 1 b 在数组的每个位置i 0 i n 搜索成功的概率相同 均为p n 算法分析的基本原则 2020 1 21 36 非递归算法 1 for while循环循环体内计算时间 循环次数 2 嵌套循环循环体内计算时间 所有循环次数 3 顺序语句各语句计算时间相加 4 if else语句if语句计算时间和else语句计算时间的较大者 2020 1 21 37 templatevoidinsertion sort Type a intn 插入排序 Typekey costtimesfor inti 1 i 0 c7n 1 在最好情况下 ti 1 for1 i n 在最坏情况下 ti i 1 for1 i n 对于输入数据a i n i i 0 1 n 1 算法insertion sort达到其最坏情形 因此 递归算法复杂性分析 2020 1 21 40 intfactorial intn if n 0 return1 returnn factorial n 1 递归分析原则 对于递归算法 一般可把时间代价表示为一个递归方程 解这种递归方程最常用的方法是进行递归扩展 通过层层递归 直到递归出口 然后再进行化简 2020 1 21 41 2020 1 21 42 例如 有某递归算法 当n 1时是递归出口 执行的时间是一个常量 当n 1时 可以把问题分解成a a 1 个子问题的递归计算 每个子问题的规模是原来问题的b b 1 分之一 分解问题和合并子问题解的花费为d n 整个问题的时间代价可以表示为下面一类递归方程的计算 递归扩展过程如下 2020 1 21 43 2020 1 21 44 设 k 则又设d x 为 积性函数 d x y d x d y 则有 2020 1 21 45 以下分三种情况讨论 1 d b 则 2020 1 21 46 2 d b 则 2020 1 21 47 3 d b 则 2020 1 21 48 求快速排序法的时间代价 此算法的递归方程可表示为 T n T n 2 n 这里 d x 是积性函数 因为 d b 所以 2020 1 21 49 讨论题 你正在对不同的玻璃样品做强度测试以确定他们从多高的高度掉下来而仍旧不碎 对某类特定的瓶子如下设计这样一个实验 你有一个具有n个横档的阶梯 并且你想找出最高的横档 能使一个瓶子的样品那哪里下落而不被摔破 你如何做 2020 1 21 50 解答 二分搜索方法 时间复杂度为Log n 但是缺点是你可能摔破一大堆的瓶子 如果主要目标是保护瓶子 从第一个横档开始让瓶子下落 然后第二个横档 每次向上爬一个高度知道瓶子摔破为止 这种方式只需要一个瓶子 但是可能的时间复杂度是n 时间复杂度和摔破瓶子之间是个不可调和的矛盾 假设只给你2个瓶子 描述一种找到最高安全横档的策略 2020 1 21 51 作业 构建一个模型求解3分之2猜想并用计算机程序实现 2020 1 21 52 算法设计技术1 分治法分治法 DivideandConquer 是把一个规模为 的问题分成两个或多个较小的与原问题类型相同的子问题 通过对子问题的求解 并把子问题的解合并起来从而构造出整个问题的解 即对问题分而治之 如果子问题的规模仍然相当大 可以对此子问题重复地应用分治策略 2020 1 21 53 分治法实例 二分法检索就是我们所学过的应用分治策略的典型的例子 快速排序算法 合并排序算法 梵塔问题等都可以用分治策略求解 快速排序算法每趟把一个元素放入排完序后它所应在的位置 这个位置把原表分成了两个宏观有序的子表 合并排序算法是把规模为 的问题分成规模为 n 2 的两个子问题 梵塔问题分原问题为两个规模为n 1的子问题 2020 1 21 54 算法设计技术2 贪心法 贪心法是一种不追求最优解 只希望得到较为满意解的方法 贪心法常以当前情况为基础作最优选择 而不考虑各种可能的整体情况 所以贪心法不要回溯 求着色问题近似解的贪心法 greedy 基本思想为 先用一种颜色给尽可能多的结点上色 然后再用另一种颜色在未着色的结点中给尽可能多的结点上色 如此反复直到所有结点都被着色为止 Dijkstra的最短路径算法 求从源点到其它各结点的最短路径 它总是从那些最短路径还不知道的结点中挑选一个到源点最近的结点 2020 1 21 55 算法设计技术3 动态规划法有些问题常常在分解时会产生大量的子问题 同时子问题界限不清 互相交叉 因而可能重复多次解同一个子问题 解决这种重复的方法 可以在得到每个子问题的解 包括其子子问题的解 时 把解保留在一个表格中 遇到相同的子问题时 就从表中找出来直接使用 这种方法就是动态规划法 DynamicProgramming 2020 1 21 56 动态规划法优势 问题的规模越大 用动态规划法的好处就越明显地体现出来 填完整个表 得到题目所求 花的时间要大大快于不填表递归的求解所花的时间 2020 1 21 57 例题 求组合数 组合数有这样的一个递推式 每次求解可将其分为两个子问题和 把按递推式分解得到下图的二叉树结构 2020 1 21 58 2020 1 21 59 首先 将 的位置上以及 0的位置上元素皆填为1 填某一中间表目时 只要把它右边表目的元素与右下方表目的元素之和填入即可 这样 很快就能求出 10 动态规划法与贪心法区别 区别1动态规划法先求子问题的解 然后通过求解子问题构造原问题的解 而贪心算法是直接地解原问题 区别2动态规划法通过对若干局部最优解的比较 去掉了次优解 从而产生了更高一层次的局部最优解 相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解 因而最终产生一个最高层次的局部最优解 而贪心法每阶段只作一个挑选 各阶段的解一经选出就固定不变了 后阶段的局部最优是基于前阶段的挑选 所以往往只能求出次优解 2020 1 21 60 动态规划法与分治法比较 共同点是 把一个大问题分解为若干较小的子问题 通过求解子问题而得到原问题的解 不同点是 分治法每次分解的子问题数目比较少 子问题之间界限清楚 处理的过程通常是自顶向下进行 动态规划法分解的子问题可能比较多 而且子问题相互包含 为了重用已经计算的结果 要把计算的中间结果全部保存起来 通常是自底向上进行 2020 1 21 61 算法设计技术4 回