算法设计与分析 - 总结0

掌握最大子段和问题的算法伪代码。（P83-85）

对于待排序列（5, 3, 1, 9, 8, 2, 4, 7）,画出快速排序的递归运行轨迹。 按升序排列

初始序列：5,3,1,9,8,2,4,7 第一次划分：4,3,1,2,5,8,9,7 第二次划分：2,3,1,4,5,8,9,7 第三次划分：1,2,3,4,5,8,9,7 第四次划分：1,2,3,4,5,7,8,9

排序完成，红色字体为每次划分的轴值

在有序序列9（r1,r2,```, rn）中，存在序号i ( 1<=i<=n),使得ri = i, 请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n). 参考代码：

1. #include

2. int findr(ints[],int begin,int end) 3. {

4. if(begin==end){

5. if(s[begin]==begin) return begin; 6. else return 0; 7. }else

8. {

9. int m=(begin+end)/2;

10. if(s[m]>m) return findr(s,begin,m-1); 11. else if (s[m]==m)return m; 12. else return findr(s,m+1,end); 13. } 14. 15. }

16. void main() 17. {

18. int s[]={0,1,1,2,4,6,8}; 19. cout<

第5章 减治法

了解减治法的设计思想

设计思想：原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。

掌握使用减治法的代表问题及时间复杂度：

折半查找，二叉树查找，堆排序，选择问题，淘汰赛冠军问题，假币问题；

以上问题的时间复杂度，如果减治是每次减小为原来规模的1/2，则时间复杂度一般为O(log2n)

掌握折半查找的算法伪代码描述及具体例子的查找过程，会根据折半查找的过程创建判定树。（P98-100）

会根据已知数据序列创建一个二叉查找树。（P100）

掌握堆排序算法中的两种调整堆和新建堆的方法：筛选法和插入法（P101-105） 堆调整问题：将一个无序序列调整为堆 （1）筛选法调整堆

关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？

（2）插入法调整堆

关键问题是：在堆中插入一个结点，如何调整被插入结点，使整个完全二叉树仍然是一个堆？