分治策略-databasegroup@depart-文庫吧資料
2025-01-30 11:57本頁面
【正文】 l, qr), pl?QL, qr?QR。 Divide: 1. 用 Q中點(diǎn)坐標(biāo)中位數(shù) m把 Q劃分為兩個(gè) 大小相等的子集合 Q1 = {x?Q | x?m}, Q2 = {x?Q | xm} Q1 Q2 p1 p2 p3 q3 q2 q1 m Conquer: 1. 遞歸地在 Q1和 Q2中找出最接近點(diǎn)對 (p1, p2)和 (q1, q2) Q1 Q2 p1 p2 p3 q3 q2 q1 m 2. 在 (p1, p2)、 (q1, q2)和某個(gè) (p3, q3)之間選擇最 接近點(diǎn)對 (x, y), 其中 p3是 Q1中最大點(diǎn) , q3是 Q2中最小點(diǎn)， (x, y)是 Q中最接近點(diǎn)。 ?劃分時(shí)間可直接得到 =D(n) – Conquer階段的時(shí)間復(fù)雜性 ?遞歸調(diào)用 ?Conquer時(shí)間 = aT(n/b) – Combine階段的時(shí)間復(fù)雜性 ?時(shí)間可以直接得到 =C(n) – 總之 ? T(n)=?(1) if nc ? T(n)=aT(n/b)+D(n)+C(n) otherwise – 求解遞歸方程 T(n) ?使用第二章的方法 例 1. Mergesort算法 Div ideCon querCom bine9 4 8 6 5 2 1 3 7 109 4 8 6 5 2 1 3 7 10 Mer gesort Mer gesort4 5 6 8 9 1 2 3 7 101 2 3 4 5 6 7 8 9 10T(n)=2T(n/2)+O(n) T(n)=O(nlogn) 例 2. 求一個(gè)集合中的最大數(shù)算法 29， 14， 15， 1， 6， 10， 32， 12 29， 14， 15， 1 6， 10， 32， 12 29， 14 15， 1 32， 12 6， 10 29 15 10 32 29 32 32 T(n)=2T(n/2)+1 T(n)=n1 A B n/2位 X= n/2位 C D n/2位 Y= n/2位 XY = (A2n/2 + B)(C2n/2 + D) = AC2n + ((AB)(CD)+AC+BD)2n/2 + BD 算法 1. 計(jì)算 AB和 CD； 2. 計(jì)算 n/2位乘法 AC、 BD、 (AB)(CD)； 3. 計(jì)算 (AB)(CD)+AC+BD； 4. AC左移 n位， ((AB)(CD)+AC+BD)左移 n/2位 ； 5. 計(jì)算 XY。第三章 DivideandConque
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1