Chapter02基础知识.pptVIP

第二章 基础知识 算法描述的工具——伪码 算法设计的基本技术 正确性证明的基本方法 算法复杂性的度量 算法复杂性分析的基本方法 2.1 算法描述的工具——伪码 以插入排序(algo1)为例 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ← A[j] 3 ? Insert A[j] into the sorted sequence A[1，j - 1]. 4 i ← j - 1 5 while i 0 and A[i] key 6 do A[i + 1] ← A[i] 7 i ← i - 1 8 A[i + 1] ← key 伪码采用类Pascal风格 ?表示是注释行 ←是赋值 参数传递采用传值方式 代码块可以采用Begin...End方式 2.2 算法设计的基本技术 增量式(incremental) 逐步求解的过程。 分治策略(The divide-and-conquer) 许多问题都可以递归求解。 Divide 将问题分成多个子问题； Conquer 递归地解决每个子问题； Combine将子问题的解合并成原问题的解； 例：归并排序(algo2)以分治思想设计排序算法 Divide 将n个待排序的元素划分成两个分别有n/2个元素的子序列； Conquer 对两个子序列递归地调用merge-sort进行排序； Combine 将两个有序的子序列合并成n个元素的有序序列； 算法设计的基本技术 贪心法 动态规划法 回溯法 分枝-限界法 2.3 正确性证明的基本方法 插入排序的正确性分析 在每次循环开始时，A[1，j - 1]中的元素是有序的。 证明：首先，第一次循环时，j=2，显然。 其次，我们证明每一次迭代后上述性质仍然成立。 最后，循环退出时，j=n+1，将n+1代入上述性质，得到A[1，n]是有序的。 分析算法的正确性循环是关键 循环不变性方法 初始化: 在第一次循环开始前不变性是满足的。 保持: 如果在某次迭代前不变性满足，在这次迭代后也满足不变性。 终止: 循环结束后，不变性可以提供程序正确性的有用信息。 例：归并过程的正确性 循环不变性： A[p,k-1]是有序的 A[p,k-1]是最小的k-p个元素 L[i]是L中待合并的元素中最小的 R[j]是R中待合并的元素中最小的 证明： 初始化: k=p，i=1，j=1，显然成立。 保持:如果L[i]=R[j]，那么L[i]显然是所有剩下元素中最小的，循环结束后k和i均+1。原来A[p,k-1]有k-p个，循环结束后将有k-p+1个；因此循环不变性成立，对于L[i]R[j]可以做类似的讨论。 终止: k=r+1，根据循环不变性A[p,k-1] 中有有序的k-p=r-p+1个。 2.4 算法复杂性的度量 如何判断一个算法的好坏？ 算法占用资源的多少：处理时间和存储空间 不同的机器资源的性质不同，如何给定统一的标准？ RAM机器模型: 单处理器，有限字长，无分级存储，基本的指令集（算术指令、数据移动指令、控制指令等），每种指令的执行时间为常量。 如何度量算法复杂度 复杂度是关于问题规模的函数 问题规模的度量要视具体问题而定 比如：排序可以用待排元素的个数 两个数相乘？（可以用数的位数） 时间复杂性可以用算法的基本运算的步数来度量 上界（最坏）、下界（最好）和平均 最坏情况：tj =j 代入T(n) 平均情况： tj =j/2 如何比较算法 的复杂度？ 找出复杂度函数中的主要因素 增长最快的部分 分治法的基本步骤 分解： 将问题分成多个子问题； 解决：递归地解决每个子问题； 合并：将子问题的解合并成原问题的解； Binary search 在有序数组中查找一个元素： 1. 分解: Check middle element. 2. 解决: Recursively search 1 subarray. 3. 合并: Trivial. Example: Find 9 Binary search 在有序数组中查找一个元素： 1. 分解: Check middle element. 2. 解决: Recursively search 1 subarray. 3. 合并: Trivial. Example: Find 9 Binary search 在有序数组中查找一个元素： 1. 分解: Check middle element. 2. 解决: Recursively search 1 subarray. 3. 合并: Trivia