03基本算法设策略.pptVIP

入队算法描述与分析 ENQUEUE(Q, e) 1 if heap-size[Q]=length[Q] 2 then error 堆上溢 3 i←heap-size[Q] ← heap-size[Q] + 1 4 A[i] ← e 5 while i 1 and A[PARENT(i)] A[i] 6 do exchange A[i] ? A[PARENT(i)] 7 i ← PARENT(i) 运行时间为T(n)=Θ(lgn) )= ?(h)，其中h为树的高度。 出队算法描述与分析 DEQUEUE (Q) 1 if heap-size[Q] 1 2 then error 堆下溢 3 max ← Q[1] 4 Q[1] ← Q[heap-size[Q]] 5 heap-size[Q] ← heap-size[Q] - 1 6 MAX-HEAPIFY(Q, 1) 7 return max 运行时间为T(n)=Θ(lgn) )= ?(h)，其中h为树的高度。 第3章 基本算法设计策略 3.1 渐增型算法 所谓渐增型算法，指的是算法使问题的解从较小的部分渐渐扩张，最终成长为问题的完整解。运用渐增型策略的算法有一个共同的特征：构成算法的主体是一个循环结构，它逐步将部分解扩张成一个完整解。该循环将遵循一个始终不变的原则：每次重复之初，总维持着问题的一个部分解。我们将此特征称为算法的循环不变量。利用循环不变量来证明渐增型算法的正确性是软件正确性证明的一个很好的方法。 有序序列的合并问题 输入：序列A[p..r]。其中，子序列A[p..q]和A[q+1..r]是有序的。 输出：A[p..r]所有元素的重排，使之有序。 算法的伪代码描述 MERGE(A, p, q, r) 1 n1←q - p + 1 2 n2 ←r - q 3创建数组L[1…n1]和R[1…n2] 4 for i ← 1 to n1 5 do L[i] ← A[p + i - 1] 6 for j ← 1 to n2 7 do R[j] ← A[q + j] 8 i ←1 9 j ←1 10 k ←p 11 while i ? n1 and j? n2 12 do if L[i] ≤ R[j] 13 then A[k] ←L[i] 14 i ←i + 1 15 else A[k] ←R[j] 16 j ←j + 1 17 k←k+1 18 if i n1 19 then 将L[i.. n1]复制到A[k..r] 20 if j n2 21 then 将R[j.. n2]复制到A[k..r] 循环不变量 在第12～17行的while循环的每次重复之初，子数组A[p..k - 1]包含L[1..n1]和R[1 ..n2]中的k - p个最小的元素，并排好序。此外，L[i]和R[j]分别是各自数组中尚未复制回数组A的元素中的最小者。 算法的运行时间 假定A[p..r]含有n（=r-p+1）个元素。第4～5行及第6～7行的for循环均重复n次。此外，第12～17行的while循环重复k-p次，第18～21行中的for循环将重复r-p+1次，两者一共耗时Θ(n)。所以算法的最坏情形时间为Θ(n)。 序列的划分问题 输入：表示成序列的全序集A[p..r] 输出：下标q（p ≤ q ≤ r），原序列A[p..r]的一个重排：使得A[p..q]中的元素值不超过A[q]，而A[q+1..r]中的元素值均大于A[q]。 算法的伪代码描述 PARTITION(A, p, r) 1 x ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5 then i ← i + 1 6 exchange A[i] ? A[j] 7 exchange A[i + 1] ? A[r] 8 return i + 1 运行时间T(n)=Θ(n)。 循环不变量 在第3~6行的for循环的每次重复之初，对每一个数组下标k： (1)若 p ≤ k ≤ i, 则A[k] ≤ x。 (2)若 i + 1 ≤ k ≤ j - 1, 则A[k] x。 (3)若 k = r, 则A[k] = x。 3.2 分治算法 分治策略在每一层递归包括三个步骤： 分解。将问题分解成若干个子问题。 治理。递归地解决各子问题。不过，若子问题的规模足够小，就以直接的方式（不再递归）解决子问题。 合并。将子问题的解合并成原问题的一个解。 排序问题描述 输入：表示成序列的全序集a1, a2, ...