第十章on-linealgorithms(存儲版)
【正文】 于是 , 算法的近似比為 L/l?O(logn). HIT CSamp。E ? 算法 A 初始化 : 構(gòu)造 m對平行線 , 斜率為 0, tan(?/m), …, tan((m 1)?/m)。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。 For k=3 To n Do input(vk)。E 我們首先定義一組記號 : ? ={1, 2, …, n } 輸入點集合 , 輸入順序為 … 、 n. D(a, b) = 點 a和 b之間的距離 . N(a, k) = 在已經(jīng)出現(xiàn)的點中 點 a的第 k最近點 . E(LR(m)(? )) = 算法 R(m)產(chǎn)生的樹的期望長度 . 假定算法收到第 i個輸入點 i. 如果 2?i?m+1, 則 i與前 i1個點中最近點連接 , 加入樹中 . 如果 m+1?i?n, 則 i與 前 i1個點中 第 j最近點連接的概率為 1111 / i mjmim ji ?????? ??????????????于是 , 我們有 ? ??????????????? ??????????????nmimijmimR jiNiDmimjiiNiDLE2 112)( ( 1 ) )),(,(111))1,(,())(( /?HIT CSamp。 input(v2)。c o s239。 ? 每對平行線必須盡可能的靠近 HIT CSamp。E ?算法的時間復雜性 –36步需要的比較次數(shù) =1+2+… +(n1) –T(n)=O(n2) ?解的精確度 – GreedyOnlineST算法的近似比是 O(logn) 設 Tonl是算法產(chǎn)生的生成樹 , l是優(yōu)化生成樹的代價或長度 , 下邊我們來證明這個結(jié)論 算法的性能分析 HIT
語文相關(guān)推薦
鄂ICP備17016276號-1