考研复习资料大汇总(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。

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