第十章on-linealgorithms-展示頁
2025-07-30 17:16本頁面
【正文】 算法的近似比為 L/l?O(logn). HIT CSamp。E ?算法的時(shí)間復(fù)雜性 –36步需要的比較次數(shù) =1+2+… +(n1) –T(n)=O(n2) ?解的精確度 – GreedyOnlineST算法的近似比是 O(logn) 設(shè) Tonl是算法產(chǎn)生的生成樹 , l是優(yōu)化生成樹的代價(jià)或長度 , 下邊我們來證明這個(gè)結(jié)論 算法的性能分析 HIT CSamp。 5. 把 v與 V(T)之間最短邊加入 T。 2. T=0。E 問題的定義 ? 輸入 : ? S={v1, v2, …, v n}是平面上的 n個(gè)點(diǎn)的集合 ? 這 n個(gè)點(diǎn)并非一次給定 , 是逐個(gè)出現(xiàn)的 ? 輸出 ? 一個(gè) ”最小 ”生成樹 求解最小生成樹問題的 Online算法 只能是近似算法 HIT CSamp。E ? Online算法的性能 – 令 Con表示 Online算法解的代價(jià) – 令 Coff表示 Offline算法解的代價(jià) – 若 Con?f(n)Coff+c, c是常數(shù) , 則稱 Online算法的近似比為 f(n). 這個(gè)算法稱為 f(n)petitive HIT CSamp。E ? Online算法 – 在算法設(shè)計(jì)階段或執(zhí)行之前無完全信息可用 , – 輸入數(shù)據(jù)往往是實(shí)時(shí)到達(dá)的 . – 算法時(shí)而正確時(shí)而錯(cuò)誤 . – 實(shí)時(shí)算法難以給出正確解 , 一般是近似算法 . ? 實(shí)時(shí)最小生成樹問題 – 難以給出優(yōu)化解 , “最小 ”需要放棄或改為 “小 ”. – Online算法可能如下工作 : ? 當(dāng)每次一個(gè)數(shù)據(jù)到達(dá)時(shí) , 將其連接到最近的鄰居節(jié)點(diǎn) . ?下邊是一個(gè)六個(gè)實(shí)時(shí)到達(dá)節(jié)點(diǎn)的例子 . HIT CSamp。E Introduction to Online Algorithms HIT CSamp。E Introduction to Online Algorithms Online Euclidean Spanning Tree Problem Online Algorithm for Convex hull problems Randomized Online Algorithm for MST 提要 HIT CSamp。HIT CSamp。E 第十章 Online Algorithms 李建中 計(jì)算機(jī)科學(xué)與工程系 HIT CSamp。E 參考資料 《 網(wǎng)站資料 》 ? 第十章 HIT CSamp。E ? 前九章介紹的算法設(shè)計(jì)的條件 – 在算法執(zhí)行之前整個(gè)輸入數(shù)據(jù)的細(xì)節(jié)都很清楚 – 問題是在完全了解輸入數(shù)據(jù)信息條件下解決的 ? 實(shí)際應(yīng)用存在不滿足上述條件的情況 – 磁盤調(diào)度問題 – 操作系統(tǒng)的頁面調(diào)度問題 – Data streams HIT CSamp。E
語文相關(guān)推薦
鄂ICP備17016276號-1