《算法分析基本概念》PPT课件.ppt

1 第1章算法分析基本概念 2009年2月23日 2 引言历史背景算法复杂性时间复杂性空间复杂性排序选择排序插入排序自底向上合并排序冒泡排序希尔排序快速排序 3 引言 计算机科学就是算法研究 4 算法 Algorithm 解题方案的准确完整的描述 是在有限步骤内求解某一问题所使用的一组定义明确的规则 无论是解题思路还是编写程序 都是在实施某种算法 前者是推理实现 后者是操作实现 算法不是程序 但算法是用程序或伪代码来描述的 5 算法分析 AlgorithmAnalysis 算法分析研究的目标为 算法一旦转换成某种语言的程序 该程序在计算机上运行 需要多少时间和存储空间才能完成解题方案 确定一个程序的运行效率 既可使用数学分析方法 也可使用实验测试方法 可以在理论和实践二个方面作出评估 算法特征 一个算法应具有以下五个重要的特征 有穷性 一个算法必须保证执行有限点之后结束 确切性 算法的每一步骤须有确切的定义 输入 一个算法有0个或多个输入 以刻画运算对象的初始情况 这里0个输入是指算法本身定义了初始条件 输出 一个算法有一个或多个输出 以反映对输入数据加工后的结果 没有输出的算法毫无意义 可行性 算法原则上能够精确地运行 而且人们用笔和纸做有限次运算后即可完成 6 7 1 2历史背景 20世纪早期 能否用一种有效的过程 算法 来求解问题 受到广泛的关注 人们的注意力是放在问题的可解和不可解的分类上 问题的可判定性和可解性的研究领域 称为 可计算理论 数字计算机出现以后 由于有限的资源 提出了尽可能少用资源的有效算法的需求 导致出现计算复杂性的新领域 计算复杂性 是研究可解类问题的效率 效率是用解决问题所需的时间和空间来描述的 历史背景 要使计算机完成人们预定的工作 首先必须为如何完成预定的工作设计一个算法 然后再根据算法编写程序 计算机程序要对问题的每个对象和处理规则给出正确详尽的描述 其中程序的数据结构和变量用来描述问题的对象 程序结构 函数和语句用来描述问题的算法 算法和数据结构是程序的两个重要方面 8 算法是问题求解过程的精确描述 一个算法由有限条可完成或机械地执行的 有结果指令组成 指令正确地描述了要完成的任务和它们所执行的顺序 计算机按算法指令所描述的顺序使得算法的指令能在有限的步骤内终止 或终止于给出问题的解 或终止于指出问题对此输入数据无解 通常求解一个问题可能会有多种算法可供选择 选择的主要标准首先是算法的正确性和可靠性 简单性和易理解性 其次是算法所需要的存储空间少和执行更快等 9 历史背景 算法复杂性 算法的复杂性是算法效率的质量 是评价算法优劣的重要依据 一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少 所需的资源越多 该算法的复杂性越高 反之 所需的资源越低 该算法的复杂性越低 计算机的资源 最重要的是时间和空间 即存储器 资源 因而算法的复杂性有时间复杂性和空间复杂性之分 10 对于任意给定的问题 设计出复杂性尽可能低的算法是我们在设计算法过程中追求的一个重要目标责任制 另一方面 当给定的问题已经有多种算法时 选择其中之复杂性最低者 是我们在选用算法适应遵循的一个重要准则 因此 算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值 关于算法的复杂性 有两个问题要弄清楚 用怎样的一个量表达一个算法的复杂性 对于一个对定的一个算法 怎样具体计算它的复杂性 11 算法复杂性 问题 已知不重复且已经按从小到大排好的n个整数的数组A 1 n 对于给定的整数x 要求寻找一个下标 使得A j x 若找不到 则返回一个0 该问题的一个简单算法是 从头到尾扫描数组A 按照该方法 或者扫到A的第i个分量时发现满足A j x 或者扫到A的最后一个分量 经检测仍不满足A j x 12 算法复杂性 13 出循环分析 x A j 此时j n j等于n 但A n 与x尚未比较 或相等或不相等 算法1 1LinearSearch Page3 输入 n个元素的数组A 1 n 和元素x输出 如果x A j 1 j n 则输出j 否则输出0 1 j 12 while j n and x A j 3 j j 14 endwhile5 ifx A j thenreturnjelsereturn0 14 顺序搜索法分析最少比较次数为1 最多比较次数为n 二分搜索令A low high 为元素按升序排列的非空数组 数A mid 为中间元素 假定x A mid 如果x在A中 则它必定是A mid 1 A mid 2 A high 中的一个 接下来只需在A mid 1 high 中搜索x 换句话说 A low mid 中的项目在后续比较中被掉弃了 类似地 如果x A mid 只需在A low mid 1 中搜索x 由于重复进行二等分 导致了一个称为二分搜索的有效策略 15 算法1 2BinarySearch Page4 输入 n个元素的数组A 1 n 按升序排列 和元素x 输出 如果x A j 1 j n 则输出j 否则输出0 1 low 1 high n j 0 j 0表示未找到2 while low high and j 0 3 mid low high 2 表示向下取整 Page45 4 ifx A mid thenj mid5 else6 ifx A mid thenhigh mid 17 elselow mid 1 x A mid 8 endif9 endif10 endwhile11 returnj 16 A 1 14 A 8 14 A 8 10 要搜索元素x 22 首先将x与A的中间元素比较 A 1 14 2 A 7 10 由于x A 7 可以把A 1 7 掉弃 在剩余元素A 8 14 中搜索x 22 A 8 14 2 A 11 23 由于x A 11 可以把A 11 14 掉弃 考虑搜索数组 1714 81114 8910 17 A 10 在剩余元素A 8 10 中搜索x 22 A 8 10 2 A 9 15 由于x A 9 可以把A 8 9 掉弃 留在序列中仅剩一个项目A 10 22 最后找到x A 10 搜索成功完毕 若x A 10 则low high条件不成立 出循环 10 A 8 10 8910 18 二分搜索法分析假定每个三向比较 if then else 计为一次比较 显然最小比较次数为1 即搜索元素x在序列中间位置 为了计算最大比较次数 不失一般性 可假定x A high 第2次迭代 循环 前数组A中剩余元素若n是偶数 A mid 1 n 共有n 2个元素 若n是奇数 A mid 1 n 共有 n 1 2个元素 二种情况都有 A mid 1 n n 2 n 22 1 第3次迭代 循环 前数组A中剩余元素 n 2 2 n 4 n 22 n 23 1 第j次迭代 循环 前数组A中剩余元素 n 2j 1 不管找到与否 搜索x的终止条件是余下元素仅仅为1个 即 n 2j 1 1 n 10 mid 10 1 2 5 剩余元素A 6 10 共计5个 10 2 n 11 mid 11 1 2 6 剩余元素A 7 11 共计5个 11 2 19 当 n 2j 1 1 j为最大迭代次数 或称最大循环次数 或称最大比较次数 n 2j 1 1等价于1 n 2j 1 2等价于2j 1 n 2j等价于 取对数 j 1 Log2n j考虑 Log2n Log2n Log2n 1因为j是整数 故有j 1 Log2n 或j Log2n 1二者均有j Log2n 1 20 1075231111815932479122210273514 可将二分搜索法的执行描述为决策树 红色的结点是与x 22相比较的数字 序列 1457891012152223273235 log214 1 4 21 比较次数是指元素比较次数 所以在while语句中的非元素比较次数 通常不予计入 确切讲 比较次数是指布尔表达式 x A mid 的执行次数 由于if then else嵌套使用 实际元素比较最大次数应为循环 迭代 次数的2倍 即2 Log2n 1 x首先与10比较 由于22比10大 故下一步在右子树中寻找 以此类推 直至22 由于决策树的高度为 Log2n 所以二分搜索法的最大比较次数为 Log2n 1 定理1 1 Page6 对于一个大小为n的已排序数组 算法BinarySearch执行比较的最大次数为 Log2n 1 容易看出 在最坏的情况下 第一个算法要检测A的所有n个分量才能判断在A中找不到等于x的分量 在第二个算法中 最坏的情况下最多只要测A中的j 1 j log2n 个分量 就判断x是否在A中 第一个算法和第二个算法解决的是同一个问题 但在最坏的情况下 所给定的x不在A中 两个算法所检测的分量个数却大不相同 前者要n 2j个 后者只要j 1个 可见第二个算法比第一个算法高效得多 因此 解决同一个问题 算法不同 计算的工作量也不同 所需的计算时间随之不同 即算法的时间复杂性不同 22 23 选择排序法 选择算法假定有一个数组A 1 n A i n 是它的一个子数组 1 i n 编写一函数 作用为 从A i n 中选择一个最小的数A k i k n 将A i 和A k 互换 若k i 无需交换 过程Selection 参见Page8 输入 A i n 输出 A i n 其中A i 为A i n 中的最小的数 0 procedureSelection i 1 k i2 forj i 1ton3 ifA j A k thenk j4 endfor5 ifk ithen交换A i 和A k 6 endprocedure 24 选择排序算法设A 1 n 为n个元素的数组 选择排序算法如下 首先在n个元素中找到最小元素 将其存放在A 1 中 然后在剩下的n 1个元素中找到最小元素 将其存放在A 2 中 重复上述过程 直至在二个元素A n 1 和A n 中找到较小元素 将其存放在A n 1 中 算法1 4SelectionSort 参见Page8 输入 数组A 1 n 输出 按升序排列的数组A 1 n 1 fori 1ton 12 Selection i 3 endfor 25 26 选择排序算法分析这个算法执行的元素比较次数为 Page49 可以看出元素的交换次数界于0和n 1之间 由于每次交换需要3次元素赋值 因此元素赋值次数界于0和3 n 1 之间 观察结论1 3 Page8 执行算法SelectionSort所需的元素比较次数为n n 1 2 元素的赋值次数界于0与3 n 1 之间 27 插入排序 插入算法假定有一个数组A 1 n A 1 i 是它的一个子数组 1 i n A 1 i 1 已按升序排列 编写一函数 作用为 将x A i 插入到子数组A 1 i 中 使得A 1 i 按升序排列 依次扫描序号从j i 1到j 1的元素 将x和A j 比较 在扫描的每一步 元素都被移到序号更高的一个位置上 这种过程直到以下情况出现时终止 找到一个小于等于x A i 的元素A j 元素A 1 已扫描过 显然j 0 此时可将x插入到A j 1 28 过程Insertion 参见Page8 9 输入 A 1 i 1 已按升序排列输出 A 1 i 按升序排列0 procedureInsertion i 1 x A i 2 j i 13 while j 0 and A j x 4 A j 1 A j 5 j j 16 endwhile7 A j 1 x8 endprocedure 29 插入排序算法设A 1 n 为n个元素的数组 插入排序算法描述如下 从子数组A 1 开始 单个数可认为有序 接下来 将A 2 插入到A 1 的前面或后面 使得A 1 2 有序 然后 再将A 3 插入到A 1 2 中 使得A 1 3 有序 直到A n 插入到A 1 n 1 使得A 1 n 有序 算法1 6InsertionSort 参见Page8 9 输入 数组A 1 n 输出 按升序排列的数组A 1 n 1 fori 2ton2 Insertion i 3endfor 30 插入排序算法分析执行InsertionSort 元素比较次数取决于输入元素的顺序 当元素已按升序排列时 元素比较次数最小 仅为n 1 每个元素A i 2 i n 只和A i 1 比较 当元素已按降序排列 并且所有元素各不相同 比较次数为最大 如下所示 因为每个元素A i 2 i n 都和子序列A 1 i 1 中的每个元素比较 这一结果与算法SelectionSort相一致 31 观察结论1 4 Page9 执行算法InsertionSort的元素比较次数在n 1到n n 1 2之间 元素赋值次数等于元素比较次数加上n 1 即2 n 1 至n n 1 2 n 1 之间 32 选择排序法 和 插入排序法 小结 1 选择排序法 往后选择 Seletion i 从A i n 中选择一个最小的数 1 i n 1 将其和A i 交换 显然A i A i 1 当i 2时 故A 1 i 有序 然后i增1 排序过程直至i n 1结束 2 插入排序法 向前插入 Insertion i A 1 i 1 已有序 2 i n 将A i 中的元素插入到A 1 i 1 中一个的合适位置 使得A 1 i 有序 然后i增1 排序过程直至i n结束 33 合并二个已排序的表 算法描述假定有一个数组A 1 m p q r是它的三个索引 并有1 p q r m 二个子数组A p q 和A q 1 r 各自按升序排列 重新排列A中元素的位置 使得子数组A p r 按升序排列 使用二个指针s和t 初始化时s p t q 1 s和t各自指向A p 和A q 1 空数组B p r 用作暂存器 每一次比较元素A s 和A t 将小的元素添加到B中 然后更新指针 若A s A t 则s加1 否则t加1 当s q 1 说明子数组A p q 的全部元素已进入B 无需再比较 此时把子数组余下部分A t r 添加到B中 当t r 1 说明子数组A q 1 r 的全部元素已进入B 无需再比较 此时把子数组余下部分A s q 添加到B中 最后将B p r 复制到A p r 34 过程Merge A 1 m p q r Page6 7 输入 数组A 1 m 和它的三个索引p q r 1 p q r m 二个子数组A p q 和A q 1 r 各自按升序排列 输出 子数组A p r 按升序排列 1 comment B p r 为辅助数组 或B 1 m 2 s p t q 1 k p s和t分别指向数组A二个子数组元素3 while s q and t r k指向数组B当前空白元素位置4 ifA s A t thenB k A s s s 15 elseB k A t t t 16 endif7 k k 1 指向数组B下一个空白位置8 endwhile9 ifs q 1thenB k r A t r 子数组A p q 元素已处理完10 elseB k r A s q 否则t r 1 子数组A q 1 r 已处理完 11 endif12 A p r B p r 复制 35 q r 8 k 1 t 4 s 1 p A p r A p q A q 1 r 2 3 16 7 11 13 45 57 B p r 2 3 7 11 13 16 45 57 36 算法分析设有个数分别为n1和n2的二个子数组n1 n2 n 如果子数组A p q 中每个元素均小于另一个子数组A q 1 r 中的所有元素 例 要合并下面二个子数组 该算法只需执行3次比较 即n1次比较 另一方面 比较次数最多为n 1 n1 n2 1次 例如要合并下面二个子数组 就需要7次比较 所以 算法Merge的最少比较次数是n1 最大比较次数为n 1 37 观察结论1 1 Page7 执行算法Merge 将个数分别为n1和n2的非空数组合并成一个为n n1 n2的排序数组 设n1 n2 元素的比较次数在n1和n 1之间 特例 如果二个数组大小为 n 2 和 n 2 需要比较的最大次数在 n 2 和n 1之间 观察结论1 2 Page7 执行算法Merge 将个数分别为n1和n2的非空数组合并成一个为n n1 n2的排序数组 元素的赋值次数恰好是2n 38 自底向上合并排序 引入插入和选择排序法的最大比较次数都与n2成正比 从这个意义上来说二种算法的效率都是比较低的 考虑下面的排序方法 39 自底向上合并排序算法 设A 1 n 为需排序的n个元素的数组 第1次迭代生成个数为2 21 的排序序列 该序列共有 个 若剩余1个元素 则让它进入下一轮合并 40 第2次迭代生成个数为4 22 的排序序列 共有 个 若剩余1或2个 则让它进入下一轮合并 如果剩余3个 则将2个元素 已排序 和另外1个元素合并成一个3元素的排序序列 41 剩余元素为7个 第j次迭代 假设j 3 生成元素个数为2j个的排序序列 该序列共有个 可能剩余的元素个数r 其大小在1至2j 1之间 j 3 r 1 7 若1 r 2j 1 j 3 r 1 4 则让它们进入下一次合并 局部已有序 若2j 1 r 2j j 3 r 5 7 则将2j 1个元素 局部已有序 和另外r 2j 1个元素 局部已有序 合并成个数为r的排序序列 总的迭代次数k的值范围为 2k 1 n 2k k 1 log2n k 42 算法1 6BottomUpSort Page10 输入 n个元素的数组A 1 n 输出 按升序排列的数组A 1 n 1 t 12 whilet n3 s t t 2s i 0 i表示要处理数据的起始地址 简称位移 4 whilei t n5 Merge A i 1 i s i t Merge A p q r 6 i i t i表示要处理数据的起始地址 简称位移 7 endwhile8 ifi s nthenMerge A i 1 i s n endwhile 起始地址 被合并前子序列长度 n 则合并 s为被合并的子序列长度 初始时为1 每循环一次乘以2 t为s的二倍 即二个子序列合并后的长度 可省略 见下页 当n不是t的整数倍 出内层循环后执行第8步 如果剩余元素数目大于s 就要将最后一个长度为s的子序列和剩余元素进行一次合并排序 此时二个子序列合并后的长度小于t 2s 43 示例当n不是2的整数幂时 自底向上合并排序的过程如下所示 44 第1次迭代 t 1 n 11成立s 1 t 2i值的范围 0 2 4 8 10i 0MERGE A 1 1 2 i 2MERGE A 3 3 4 i 4MERGE A 5 5 6 i 6MERGE A 7 7 8 i 8MERGE A 9 9 10 i 10时 i t 12 11不成立 出循环 出循环后 i s 10 1 11 n 11不成立 因此不再合并 最后一个序列长度为1 或称剩下的元素个数 MERGE A i 1 i s i t s表示被合并序列的长度 即合并前 t表示合并后序列的长度 初值为1 i表示位移 1 2 3 4 5 6 7 8 9 10 11 45 第2次迭代 t 2 n 11成立s 2 t 4i值的范围 0 4 8i 0MERGE A 1 2 4 i 4MERGE A 5 6 8 i 8时 i t 11不成立 出循环 出循环后 i s 8 2 n 11成立 执行MERGE A 9 10 n 最后一个序列长度为3 MERGE A i 1 i s i t s表示被合并序列的长度 即合并前 t表示合并后序列的长度 初值为1 i表示位移 1 2 3 4 5 6 7 8 9 10 11 46 第3次迭代 t 4 n 11成立s 4 t 8i值的范围 0 8i 0MERGE A 1 4 8 i 8时 i t 11不成立 出循环 出循环后 i s 8 4 n 11不成立 因此不再合并 最后一个序列长度为3 MERGE A i 1 i s i t s表示被合并序列的长度 即合并前 t表示合并后序列的长度 初值为1 i表示位移 1 2 3 4 5 6 7 8 9 10 11 47 第4次迭代 t 8 n 11成立s 8 t 16i值的范围 0i 0时 i t 11不成立 出循环 出循环后 i s 0 8 n 11成立 执行MERGE A 1 8 n MERGE A i 1 i s i t s表示被合并序列的长度 即合并前 t表示合并后序列的长度 初值为1 i表示位移 第5次迭代 t 16 n 11不成立 程序终止执行 1 2 3 4 5 6 7 8 9 10 11 48 自底向上合并排序算法分析 假设数组元素个数n为2的幂 n 2k 2logn 外部循环次数为k log2n 在执行内部循环后 由于n为2的幂 故第8步永远不会执行 在第1次迭代中 共执行了n 2次比较 n个元素被划分为n 2个段 段长 2 段内有序 在第2次迭代中 n 2个段 段长 2 元素序列被合并成n 4个段 段长 4 段内有序 根据观察结论1 1 Page7 每对合并需要的比较次数 最少为2 最多为3 在第3次迭代中 n 4个段 段长 4 元素序列被合并成n 8个段 段长 8 段内有序 根据观察结论1 1 Page7 每对合并需要的比较次数 最少是4 最多7 49 最少比较次数 k log2n 在第j次迭代中 个段 段长 2j 1 元素序列被合并成个段 段长 2j 段内有序 根据Page7观察结论1 1 Page7 每对合并需要的比较次数 最少是2j 1 最多为2j 1 50 最多比较次数 k log2n 51 观察结论1 5 Page11 用算法BottomUpSort对n个元素进行排序 当n为2的整数幂时 比较次数在 nlog2n 2到nlog2n n 1之间 执行该算法的元素赋值次数为2nlog2n 52 时间复杂性 在计算复杂性领域中 主要是研究一个算法所需要的时间和空间 即当给出合法的输入时 为了得到输出 该算法执行时所需要的时间和空间 其中时间尤为重要 执行算法BottomUpSort的最大比较次数nlog2n n 1执行算法SelectionSort的最大比较次数n n 1 2假设一次比较所需的时间为10 6秒 当数据个数n分别为27 128和220 1048576时 二个算法执行所耗费的时间上限如下表所示 53 概述称 一个算法A对于输入x要用y秒来运行 是没有意义的 也是没有必要的 因为影响一个算法的实际运行时间与诸多因素有关 例机器性能 语言选择 编译程序优劣 程序员素质等 甚至无需计算出算法运行时间的近似数 理由如下 算法分析通常是将解决同一问题的各种算法之间进行相互比较 执行时间是相对的 而不是绝对的 算法可以用各种语言来表示 甚至使用人类语言 算法应独立于机器 无论科技如何进步 对算法运行时间的评估始终成立 算法分析不拘泥小规模数据的输入 主要关心在大的输入实例时 算法运行状况 例某一算法运行时间为2n3 当n变得很大时 常数2将不起作用 观察函数n2log2n 10n2 n中的低阶项10n2和n 当n值越大 10n2 n对函数值的影响就越小 54 为了简化对算法过程的分析 常常会忽略算法中每条语句的真实代价 而用常量ci表示 在进一步的简化抽象中 即对运行时间的增长率简化 在简化过程中 仅考虑公式中的最高次项 如 an2 bn c简化为an2 因为当很大时低阶项便显得不太重要 另外 还可以忽略最高次项的常数系数 因为在考虑较大规模输入下的率相对于增长率来说系数是次要的 55 渐近运行时间去除表示算法运行时间函数的低价项和首项系数 常数 时间复杂性在算法分析中 通常是用渐近运行时间来度量一个算法 渐近运行时间通常称为时间复杂性 算法分析中的渐近符号有 O o 表示时间复杂性的常用函数有 常数 1运行时间为恒定值 和输入无关 次线性函数 log2n 简记为logn 线性函数 n次平方函数 nlog2n 简记为nlogn 平方函数 n2立方函数 n3指数函数 2n运行时间是爆炸性的阶乘函数 超指数函数 n 运行时间是爆炸性的 56 定义1 2 Page16 令f n 和g n 是从自然数集到非负实数集的二个函数 如果存在一个自然数n0和一个正常数c 使得n n0 f n cg n 则称f n O g n n0称为阈值 O符号 读作大O 若极限为非0正常数 则函数f n 和g n 增长速度至多相差常数倍 或称为同一级别 若极限为0 说明随着n的增大 函数f n 的增长要比g n 的增长慢得多 正常数 可以是0 57 例1 f n 3n 2 求g n 使得f n O g n 解1 当n 2 f n 3n 2 3n n 4n令g n n 当n 2时有f n 4g n f n 4g n f n O g n O n 解2 令g n n 同理可证 f n O nk k 1 g n 通常为上限最小值 即k 1 58 例2 f n 10n2 4n 2 求g n 使得f n O g n 解1 当n 2 有f n 10n2 4n n 10n2 5n当n 5 有f n 10n2 5n 10n2 n2 11n2令g n n2 因为当n 5时有f n 11g n 所以f n O g n O n2 解2 令g n n2 同理可证 f n O nk k 2 59 例3 f n 6 2n n2 求g n 使得f n O g n 解 当n 4 有n2 2n故当n 4 有f n 6 2n n2 6 2n 2n 7 2n令g n 2n 因为当n 4时有f n 7g n 所以f n O g n O 2n O符号提供了运行时间的上界 算法InsertionSort执行的比较次数最多为cn2 n n 1 2 0 5n2 0 5n c为某个适当选择的常数 则称该算法的运行时间是O n2 只要当排序元素的个数不小于某个阈值n0时 运行时间最多为cn2 应强调的是 即使当输入很大时 也不能说运行时间恰好为cn2 因为当输入已经按升序排列 排序算法InsertionSort执行的比较次数为n 1 60 符号 读作omiga 定义1 3 Page16 令f n 和g n 是从自然数集到非负实数集的二个函数 如果存在一个自然数n0和一个正常数c 使得n n0 f n cg n 则称f n g n n0称为阈值 若极限是一个正常数 说明函数f n 的增长速度和函数g n 相差整数倍 基本为同一级别 若极限为 说明随着n的增大 函数f n 增长的速度要比g n 快得多 可以是正常数或 61 例1 f n 3n 2 求g n 使得f n g n 解 当n 0 f n 3n 2 3n 令g n n 因为当n 0时有f n 3g n 所以f n g n n 例2 f n 10n2 4n 2 求g n 使得f n g n 解 令g n n2 62 在常数因子范围内 O符号提供了运行时间上界 而 符号提供了运行时间下界 排序算法InsertionSort的元素比较次数至少是 n 1 在这种情况下 称算法InsertionSort的运行时间是 n 无论何时 当排序元素个数不小于某一个阈值n0时 运行时间至少是cn 称排序问题的比较次数为 nlogn 是指无法设计出一个新的基于比较的排序算法 它的时间复杂性小于nlogn 符号定义的一个重要推论 f n g n 当且仅当g n O f n 63 符号 读作theta 定义1 4 Page16 令f n 和g n 是从自然数集到非负实数集的二个函数 如果存在一个自然数n0和二个正常数c1和c2 使得n n0 c1g n f n c2g n 则称f n g n n0称为阈值 符号定义的一个重要推论 f n g n 当且仅当f n O g n 并且g n O f n 极限是一个正常数 说明函数f n 的增长速度和函数g n 的增长速度相差整数倍 基本为同一级别 64 例 f n 3n 2 求g n 使得f n g n 解 当n 2 f n 3n 2 3n n 4n当n 1 f n 3n 2 3n故当n 2 有3n f n 4n令g n n 因为当n 2时有3g n f n 4g n 所以f n n 解2 令g n n 65 符号提供了算法运行时间的精确描述 由于算法InsertionSort的运行时间由线性到平方排列 因此不能用 描述 而SelectionSort算法和BottomUpSort算法可分别使用 n2 和 nlog2n 精确描述 f n g n 是一个等价关系 由这个关系导出一个等价类 称为复杂性类 例 f n 3n 2 g n n 显然有f n g n 表示这二个函数属同一复杂性类 o符号 读作小o 由等价关系f n g n 导出了一个等价类 为了说明二个函数属于不同类 引入了o符号 f n o g n 当且仅当f n O g n 但g n O f n 66 定义1 3 Page19 令f n 和g n 是从自然数集到非负实数集的二个函数 如果对于每一个常数c 0 存在一个自然数n0 使得n n0 f n cg n 则称f n o g n 形式地说明了当n 时 f n 对于g n 来说可以忽略不计 f n o g n 当且仅当f n O g n 但g n O f n 例如 n是o n2 的 等价于 n是O n2 但n2 O n 67 68 我们用f n g n 来表示f n 是o g n 的 用该记号可简明地表示复杂性的层次 1 logn n1 2 n nlogn n2 n3 2n n 类似于 类似于 类似于 o类似于 不要将确切的关系和渐近符号相混淆 例如 100n n100n O n n 100n100n n n 100n100n n 一般地 设f n aknk ak 1nk 1 a1n a0 则f n nk 它蕴含着f n O nk f n nk 69 例1 5 Page17 f n 10n2 20n 求g n 使得f n g n 解 当n 1 f n 10n2 20n 30n2 f n n2 当n 1 f n 10n2 20n n2 f n n2 故当n 1 有n2 f n 30n2令g n n2 因为当n 1时有g n f n 30g n 所以f n n2 解2 令g n n2 70 例1 6 Page17 令f n aknk aknk akn a0 则f n nk f n nk f n nk 例1 7 Page17 例1 9 Page17 任一常函数是 1 1 1 71 证明当n 时有2n n 证 由此可得 2n o n 72 例1 12 Page17 73 例1 14 Page18 同理 74 75 1 9空间复杂性空间复杂性定义 P19 为了求解问题的实例 执行计算步骤所需要的内存空间的数目 它不包括分配用来存储输入的空间 换句话说 仅仅是算法需要的工作空间 空间复杂性的计算要比时间复杂性简单得多 可将时间复杂性的定义和符号移植到空间复杂性的表示 例1 在算法LinearSearch中 仅需要一个内存单元保存搜索结果 如果加上局部变量 可以得出需要的空间数量为 1 同理算法BinarySearch SelectionSort和InsertionSort 76 例2 在算法Merge中 需要和输入大小相同的存储器n个 因此空间复杂性为 n 同理算法BottomUpSort 许多问题的处理需要在时间和空间之间平衡 一般来说 给算法分配的空间越大 算法运行速度就越快 反之亦然 迄今为止所讨论的大多数算法中 增加空间并不可能导致算法速度的加快 有可能反而降低 但是 减小空间会导致算法速度的降低是毫无疑问的 77 1 11如何估计算法运行时间通