算法分析與設(shè)計—貪心算法論-資料下載頁
2025-06-04 10:51本頁面
【正文】 1， S2? ， Sk，用 2 路合并算法將這 k 個序列合并成一個序列 。 假設(shè)所采用的 2路合并算法合并 2個長度分別為 m和 n的序列需要m+n1次比較。試設(shè)計一個算法確定合并這個序列的最優(yōu)合 并順序，使所需的總比較次數(shù)最少。為了進(jìn)行比較，還需要確定合并這個序列的最差合并順序，使所需的總比較次數(shù)最多。 原理分析 這個程序比較適合用堆，最優(yōu)用最小堆，最差用最大堆 ； 以最優(yōu)合并為例 ： （ 1） 使用各序列的長度建堆 ； （ 2） 兩個最小的元素出堆 ， 計算這兩序列合并需要的比較次數(shù) ， 該次數(shù)入堆 ； （ 3） 重復(fù) （ 2）， 直到堆只剩下一個元素 ； 最后剩下的元素即為題目的解 。 算法時間復(fù)雜度分析 復(fù)雜度為 O(nlogn)， 排序后 ， 最小的兩個序列是前兩個 ， 計算最小的兩個序列的合并次數(shù)后，該次數(shù)不一定是新的最小的兩個序列之一 ， 所以在下一次合并前，必需使數(shù)組仍舊有序，讓最小的兩個序列在數(shù)組的最前面 ， 為使數(shù)組重新有序 ， 可以使用類似插入排序的插入過程，將新得到的數(shù)字直接插入到數(shù)組 ， 這樣不需要額外的儲存空間，但總復(fù)雜度是 O(n2)，考慮到需要計算最優(yōu)與最差，實(shí)際上也必須需要額外的 O(n)的空間來保存排序后的結(jié)果 ， 如果將排序后的數(shù)組按照順序作成一個鏈表 ， 那么鏈表的最前的兩節(jié)點(diǎn)就是最小的兩序列 ， 計算合并次數(shù) ， 刪除該兩節(jié)點(diǎn)，將新得到的次數(shù)插入到鏈表，注意到，后面需要插入的數(shù) 字肯定比前面插入的數(shù)字大，所以從上一次插入的位置之后查找新的插入位置 ，這樣插入數(shù)字的總的時間復(fù)雜度是 O(n)的，總的時間復(fù)雜度仍舊是 O(nlogn)，并使用了額外的 O(n)的空間 。 總 結(jié) 對于貪心算法的應(yīng)用，如果某個問題具有貪心算法的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，那么，它就可以采用貪心策略進(jìn)行分析，進(jìn)而求解，貪心算法的應(yīng)用舉例不僅只有本論文中的那幾個，他對于背包問題、最優(yōu)裝載問題、硬幣找錢問題等都是十分方便有效的算法，貪心算法在科學(xué)計算和工程中的應(yīng)用也越來越廣泛，例如用貪心算法進(jìn)行三角剖分的指紋匹配方法、貪心算法在競賽中的應(yīng)用、貪心算法在排課系統(tǒng)中的應(yīng)用、 貪心聚類算法及其在遙感圖像分類和壓縮中的應(yīng) 等 。 貪心算法是很常見的算法，貪心策略是最接近人的日常思維的一種解題策略，雖然它不能保證求得的最后解一定是最佳的，但是它可以為某些問題確定一個可行性范圍。貪心算法所作的選擇依賴于以往所作過的選擇，但決不依賴于將來的選擇，這使得算法在編碼和執(zhí)行過程中都有一定的速度優(yōu)勢。對于一個問題的最優(yōu)解只能用窮舉法得到時，用貪心算法是尋找問題最優(yōu)解的較好算法。對一個問題可以同時用幾種方法解決，貪心算法并不是對所有的問題都能得到整體最優(yōu) 解或是最理想的近似解時，就需判斷貪心性質(zhì)的正確性了。與回溯法、動態(tài)規(guī)劃法等比較，它的適用區(qū)域相對狹窄許多?？傊?，如果一個貪心解決方案存在，就可以使用它。 參考文獻(xiàn) [1]王曉東 .算法分析與設(shè)計（第 3版）清華大學(xué)出版社 [2] [M].北京 :電子工業(yè)出版社 [3] 殷建平 .關(guān)于貪心算法的正確性證明 [M].江西師范大學(xué)學(xué)報（自然科學(xué)版） 北 華 大 學(xué) 算法分析與設(shè)計論文 題 目： 貪心算法的應(yīng)用 姓 名 ： 王晗雪 畢業(yè)學(xué)院 ： 計算機(jī)科學(xué)技術(shù) 學(xué)院 專業(yè)班級 ： 軟 件 132 班 學(xué) 號 ： 202117020223 指導(dǎo)教師 ： 劉錫祥
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1