算法分析与设计AlgoDALectureNotesW4章节.pptVIP

Last Section KRUSKAL(G, w) _Disjoint Set A ← for each vertex v ∈ V [G] do MAKE-SET (v) sort the edges of E by nondecreasing weight w for each edge (u, v) ∈ E, in order by nondecreasing weight do if FIND-SET (u) ≠ FIND-SET (v) then A ← A ∪ { (u, v)} UNION(u, v) Return A Disjoint Set Linked list: Θ(m2) weighted union: m+nlogn Disjoint-set Forest with union-by-rank and path compression: KRUSKAL: ElogE Another Implementation of Prim’s Algorithm D (G, w, r) Q ← V[G] // build heap for each u ∈ Q do key [u] ← ∞ key[r] ← 0 π[r]← NIL while Q ≠ Φ do u ← EXTRACT – MIN(Q) // O(V)O(lgV), for each v ∈ Adj[u] //2E do if v ∈ Q and w(u, v) ＜ key[v] then π[v] ← u key[v] ← w [u, v] O(V), O(V)O(lgV), 2EO(lgV). Divide and Conquer 合并排序 将待排序数组对半分成两个子数组； 分别对两个子数组排序； 将两个已排序的子数组合并。 合并排序 MERGESORT 输入：n个元素的数组A[1…n]。 输出：按非降序排列的数组A[1…n]。 mergesort(A, 1, n) Procedure mergesort (A, low, high) if low high then mid ← mergesort (A, low, mid) mergesort(A, mid + 1, high) MERGE(A, low, mid, high) end if 合并排序效率 假定n 是2的幂，即n = 2k, k 是大于等于0的整数。 如果n = 1, 则算法不执行任何元素的比较 如果n 1, 则执行了步骤2到步骤5，执行步骤3和步骤4需要的元素比较次数都为C(n/2)。 合并两个子数组所需的元素比较次数在n/2 与n – 1 之间 Algorithm MERGE 输入：数组A[1..m]，索引1≤p ≤ q r ≤ m，两个子数组A[p..q]和A[q+1..r] 分别非降序排列 输出：合并A[p..q]和A[q+1..r]的数组A[p..r] B[p..r]为辅助数组 1. s←p; t←q+1; k←p; 2. while s ≤ q and t ≤ r 3. If A[s] ≤ A[t] then 4. B[k] ← A[s] 5. s ← s+1 6. else 7. B[k] ← A[t] 8. t ← t+1 9. end if 10. k ←k+1 11. end while 12. If s=q+1 then B[k..r] ← A[t..r] 13. else B[k..r] ← A[s..q] 14. end if 15. A[p..r] ← B[p..r] * n1+n2=n, n1 ≤n2, 则 n1 ≤ c(n)≤ n-1 合并排序效率 算法所需的最大比较次数由下列递推式给出 C(n) = 0 若n =1 = 2C（n/2） + n – 1 若n ≥ 2 C(n)=nlogn – n + 1 合并排序效率 算法所需的最小比较次数由下面的递推式给定 C(n) = 0 若n = 1 =2C (n/2) + n/2 若n ≥2 合并排序效率 (a,c非负整数，b,d,x非负常数，n=ck)： f(n) =d 若 n=1 =af(n/c)+bnx 若 n=2 的解是 f(n)= bnxlogcn + dnx 若 a=cx f(n)= 若 acx 合并排序效率 最小比较次数 C(n)=(nlogn)/2 因(a,c非负整数，b,d,x非负常数，n=ck)： f(n) =d