乔林.pptVIP

Modern Operating System 乔 林 第十一章 算法设计与分析 学习目标 了解大多数问题都可以用几种不同的算法解决 掌握什么样的算法是正确的 了解解决同一问题的不同算法其性能各不相同 了解算法复杂度的概念，用它可对随着问题规模成比例增长的运行时间的变化作定性分析 学会用大“O”符号表示算法复杂度；掌握最常见的复杂度类型，并且理解每个复杂度类型的性能特点 11.1 算法的概念与特征 算法的由来 解决问题的方法与步骤 演算过程的抽象表述 算法的基本特征 有穷性：算法必须能够在有限步内终止 确定性：每一步骤的顺序和内容不能有二义性 有效性：所有操作都有明确含义并能够实现 有零个或多个输入：算法应该接受处理数据 有一个或多个输出：算法必须能够输出结果 算法举例一 3?3 幻方 用数字1~9组成3?3方阵，各行各列各对角线的数字之和为15 算法步骤 S1：把1放在第一行中间的一格 S2：在右上方斜对角线方向给出下一个自然数 在此过程中，若该数已出方框，则将其写在该行或该列另一端 S3：写完三个数后，将第四个数写在第三个数下 S4：重复上述操作， 直到格子填满为止 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例一 算法举例二 查英文词典的算法步骤 S1：翻开词典任意一页 S2：若所查词汇在本页第一个单词前，则往前翻页重复S2；若所查词汇在本页最后一个单词后，则往后翻页重复S2 S3：若非S2的情况，则依次比较本页单词，或者查出该单词，或者得出结论，查不到该单词 算法举例三 素数判定的算法步骤 S1：输入 n 的值 S2：i = 2 S3：r = n / i S4：若 r = 0，则 n 不是素数，结束；若 r ? 0 ，执行S5 S5：i = i + 1 S6：若 i ? n ? 1，返回S3；否则判定 n 为素数，结束 11.2 算法的类型与结构 数值算法与非数值算法 算法的基本结构 顺序结构 分支结构 循环结构 程序的结构化 11.3 算法的描述方法 流程图 使用流线表示程序控制流 程序逻辑清晰，绘制复杂 N-S图 去除流线与箭头的流程图 绘制复杂，逻辑不清晰 伪代码 程序逻辑较不清晰，书写简单 11.4 算法的设计与实现 算法实现过程 问题分析 按某种策略实现算法 验证上述实现确实为算法 证明算法的正确性 选择合适的策略，提高算法效率 素数判定问题 函数原型 int IsPrime( int n ); 素数判定问题的第二种算法 检查 1 到 n 的数中，是否存在可被 n 整除的数 每找到一个因子，计数器自加 1 在所有数判断完毕后，查看计数器是否为 2 若为2则为素数，否则不是 素数判定问题 素数判定问题 验证上述策略确为算法 操作步骤的描述清楚，不存在二义性 各操作确实可计算机实现 执行过程可终止 算法正确性的证明 素数至少有两个因子 divisors 表示数的因子个数，初始为 0，每找到一个因子，其值递增 1，循环依次查找全部 n 个自然数，若只有两个因子，显然为素数 素数判定问题 提高算法效率 只要在 1 和 n 之间存在一个因子就可终止，并返回 n 不是素数 若 n 可被 2 整除，不需检验其它数，程序终止并返回 n 不是素数；若否，则所有偶数都不是因子，程序只需检验奇数 程序不必检验因子一直到 n，只需到 即可 素数判定问题 素数判定问题 素数判定问题 如何选择合适的算法 选择指标 正确性 效率 可读性 可维护性 算法评估：在诸多因素中寻找平衡点 高效的算法可读性差，可读性好的算法效率一般不高 最大公约数问题 函数原型 int gcd( int x, int y); 两种算法实现策略 穷举法：逐一尝试所有可能值 欧几里德算法 步骤1：x 除以 y，余数为 r 步骤2：若 r 为 0，则 y 为所求，算法终止；否则 步骤3：将 y 作为新 x，r 作为新 y，返回第1步 最大公约数问题 穷举法实现 最大公约数问题 欧几里德算法实现 11.5 算法分析与算法复杂度 算法分析的目的 评估算法的执行效率 排序算法 选择排序 归并排序 算法复杂度 选择排序 函数原型 void SortIntegerArray( int a[], int n ); 基本原理 依次找最小元，将最小元与数组未排序的第一位互换 重复上述步骤 选择排序 原始数组 选择排序 选择排序算法的性能分析 程序执行时间 T 随问题规模 n 显著增加 算法的主要执行时间在于循环 循环执行次数 (n2+n)/2 算法执行时间的估计与测量 平方级算法执行时间：T ? n2 算法复杂度 算法复杂度的定义 算法的执行