第十章on-linealgorithms(參考版)
2025-07-24 17:16本頁面
【正文】 E 我們首先定義一組記號(hào) : ? ={1, 2, …, n } 輸入點(diǎn)集合 , 輸入順序?yàn)? … 、 n. D(a, b) = 點(diǎn) a和 b之間的距離 . N(a, k) = 在已經(jīng)出現(xiàn)的點(diǎn)中 點(diǎn) a的第 k最近點(diǎn) . E(LR(m)(? )) = 算法 R(m)產(chǎn)生的樹的期望長度 . 假定算法收到第 i個(gè)輸入點(diǎn) i. 如果 2?i?m+1, 則 i與前 i1個(gè)點(diǎn)中最近點(diǎn)連接 , 加入樹中 . 如果 m+1?i?n, 則 i與 前 i1個(gè)點(diǎn)中 第 j最近點(diǎn)連接的概率為 1111 / i mjmim ji ?????? ??????????????于是 , 我們有 ? ??????????????? ??????????????nmimijmimR jiNiDmimjiiNiDLE2 112)( ( 1 ) )),(,(111))1,(,())(( /?HIT CSamp。E 算法的時(shí)間復(fù)雜性 ? 時(shí)間復(fù)雜性 ? 每次考察需要 O(m)時(shí)間 ? 需要 O(n)次考察 ? T(n)=O(nm) HIT CSamp。 Else 從 (vk, v1), … ,(vk, vk1)中 隨機(jī)地 選擇 m條邊 , 把這 m條邊中最小邊加入 T。 For k=3 To n Do input(vk)。 input(v2)。 input(m)。E 問題的定義 ?輸入 ? Euclidean空間上的 n個(gè)點(diǎn) : v1, v2, … , vn ? n個(gè)逐個(gè)出現(xiàn) ? 輸出 ? 由 v1, v2, … , vn構(gòu)成的 最小生成樹 HIT CSamp。E 考慮下圖 , P2m P2m1 P1 P2 P3 P4 A2m A1 A2 A3 A4 由 AB+AC? BC sec(?/2)， 我們有 L(E)= P2mA1+A1P1+P1A2+… +A2mP2m ? sec(? /2m)(P2mP1+P1P2+… +P2m1P2m) = sec(? /2m)L(A). 于是 , Err(A)= (L(C)L(A))/L(C) ? (L(E)L(A))/L(A) ? sec(? /2m)1 HIT CSamp。c o s239。E ? 時(shí)間復(fù)雜性 – O(mn)=O
語文相關(guān)推薦
鄂ICP備17016276號(hào)-1