考研複習資料大彙總(ppt 42頁)

考研複習資料大彙總目錄：
一、貪心法——活動安排問題
二、貪心法——多機調度問題
三、貪心法——最優裝載
四、貪心法——汽車加油問題
五、回溯法——n皇後問題
六、回溯法——圖的m著色問題

考研複習資料大彙總內容提要：
分治法——線性時間選擇：
將n個輸入元素劃分成?n/5?個組，每組5個元素，隻可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，並取出每組的中位數，共?n/5?個。
遞歸調用select來找出這?n/5?個元素的中位數。如果?n/5?是偶數，就找它的2個中位數中較大的一個。以這個元素作為劃分基準。
設所有元素互不相同。在這種情況下，找出的基準x至少比3(n-5)/10個元素大，因為在每一組中有2個元素小於本組的中位數，而n/5個中位數中又有(n-5)/10個小於基準x。同理，基準x也至少比3(n-5)/10個元素小。而當n≥75時，3(n-5)/10≥n/4所以按此基準劃分所得的2個子數組的長度都至少縮短1/4。

..............................