《算法基础》复习提纲.doc
《《算法基础》复习提纲.doc》由会员分享,可在线阅读,更多相关《《算法基础》复习提纲.doc(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、算法基础算法基础复习提纲复习提纲 1 引言引言(ch1)1.什么是算法及其特征 2.问题实例和问题规模2 算法初步算法初步(ch2)1.插入排序算法 2.算法复杂性及其度量(1)时间复杂性和空间复杂性;(2)最坏、最好和平均情形复杂性; 3.插入排序的最坏和平均时间 4.归并排序算法及其时间复杂性 3 函数增长率函数增长率(ch3)1.渐近记号 O、 的定义及其使用 2.标准复杂性函数及其大小关系 3.和式界的证明方法4 递归关系式递归关系式(ch4)1.替换法 (1)猜测解数学归纳法证明; (2)变量变换法; 2.迭代法 (1)展开法; (2)递归树法; 3.主定理5 概率分析概率分析(ch
2、5)1.序列随机排列的两种方法及其复杂性6 堆排序堆排序(ch6)1 堆的概念和存储结构 2.堆的性质和种类 3.堆的操作:建堆;整堆; 4.堆排序算法和时间复杂性 5.优先队列及其维护操作7 快速排序快速排序(ch7)1.快速排序算法及其最好、最坏时间和平均时间 2.随机快速排序算法及其期望时间8 线性时间排序线性时间排序(ch8)1.基于比较的排序算法下界:(nlogn) 2.计数排序适应的排序对象、算法和时间 3.基数排序适应的排序对象、算法和时间 4.桶排序适应的排序对象、算法和时间9 中位数和顺序统计中位数和顺序统计(ch9)1.最大和最小值的求解方法 2.期望时间为线性的选择算法
3、3.最坏时间为线性的选择算法及其时间分析10 红黑树红黑树(ch13)1.红黑树的定义和节点结构 2.黑高概念 3.一棵 n 个内点的红黑树的高度至多是 2log(n+1) 4.左旋、右旋算法 5.插入算法、时间、至多使用 2 次旋转 6.删除算法、时间、至多使用 3 次旋转11 数据结构的扩张数据结构的扩张(ch14)1.动态顺序统计: 扩展红黑树,支持选择问题(给定 Rank 求相应的元素),Rank 问题(求元 素 x 在集合中的 Rank)(1)节点结构的扩展; (2)选择问题的算法; (3) Rank 问题的算法; (4)维护树的成本分析; 2.如何扩张一个数据结构:扩张的步骤;扩张
4、红黑树的定理 3.区间树的扩张和查找算法 12 递归与分治法递归与分治法1. 递归设计技术 2. 递归程序的非递归化 3. 算法设计 (1) 最近点对; (2) 生成全排列; (3) 大整数乘法; (4) Stranssen 矩阵乘法;13 动态规划动态规划(ch15)1.方法的基本思想和基本步骤 2.动态规划和分治法求解问题的区别 3.最优性原理及其问题满足最优性原理的证明方法 4.算法设计(1) 多段图规划; (2) 矩阵链乘法;(3) 最大子段和; (4) 最长公共子序列; (5) 0-1 问题求解; 14 贪心算法贪心算法(ch16)1.方法的基本思想和基本步骤 2.贪心算法的正确性保
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 基础 复习 温习 提纲
限制150内