算法内容-word资料(精).doc

四,考试内容 1. DC 问题的时间复杂度, 稳定性, 个别代码: 插入排序, 归并排序, 堆排序, 快速排序, 计数排序, 基数排序,桶排序 2. DP 问题:优化问题的四个步骤, 0-1 背包 3. Greedy( 贪心算法): 分数背包, 0-1 背包,霍夫曼编码图的算法: 3+1 算法,具体是单源点最短路径( Dijkstra 、 Bellman-Ford ) ,每对结点间最短路径( Flo y 算法), johnson 算法(这个算法只要知道基本思想即可) (图的算法, 3+1 ,单源最短路径:迪杰斯特拉, Bellman-Ford ;每队节点间的最短路径:弗洛伊德算法 johnson 算法) 4. 收索算法:回溯, N 皇后问题,分支和边界算法 5. plete : NP 完全问题 6. 智能收索( 邻域收索) :基本思路,算法分析 7. 算法设计:分治,动态规划,收索四,考点分析 1. 插入排序:插入排序的计算时间 T(n) : 最好情况( 输入数组已经是有序的): 计算时间是 n 的线性函数; 最坏情况( 输入数组是逆序的, 即降序): 计算时间是 n 的二次函数。原地排序(in place) ,空间开销为常数。 2. 分治法:要求解问题 P: -- 分:将问题 P 分解为规模更小的子问题 P1, P2, …, Pk。-- 治:递归求解这些子问题。-- 合并:将子问题 P1, P2, …, Pk 的解合并为问题 P 的解。 3. 归并排序:(1 )利用分治策略,可以得到一个归并排序算法-- 分:将 n 个元素分为两个 n/2 大小的子序列。-- 治:分别将两个子序列排序。-- 合并:将两个有序子序列合并,得到完整的有序序列(2 )归并排序的伪代码: (3 )归并排序简单总结: 归并排序 MERGE-SORT(A,p,r) MERGE(A,p,q,r) 归并排序分析- Θ(nlgn) ,需要的辅助存储空间为Θ(n). -- 递归树法-- 展开法-- 数学归纳法渐近分析 O- 表示法 4. 主方法: (考计算题)提供了一种快速求解下述形式递归式的方法: T(n) =a T(n/b) + f(n) 其中 a、b 为常数, a≥1且b>1, f(n) 为一渐近正函数递推式的三种基本情况: R 主定理思想: CASE 1: 开销从根到叶子等比递增。叶子开销占总体开销的固定比例部分。 CASE 2: (k= 0) logbn 层中的每层开销基本相当。 CASE 3: 开销从根到叶子等比递减。根的开销占总体开销的固定比例部分。概要重述:目前为止: -- 插入排序计算时间为Θ(n2) ; 原地排序(in place) -- 归并排序计算时间为Θ(n lg n) ;需要的辅助存储空间为Θ(n). 后续: -- 堆排序计算时间为Θ(n lg n) ;原地排序(in place). --快排平均计算时间为Θ(n lg n) ;最实用(因此也是最广泛应用)的排序算法。--Sorting in linear time. 5. 堆排序:具有 n 个元素的堆,其高度为: (1) MAX-HEAPIFY 调整堆以使其满足大顶堆的性质。 O(log n) (2) BUILD-MAX-HEAP 基于无序数组构建大顶堆。Θ(n) (3 )要完成排序,首先将数组转换成大顶堆