(算法内容.docVIP

四，考试内容 DC问题的时间复杂度，稳定性，个别代码：插入排序，归并排序，堆排序，快速排序，计数排序，基数排序，桶排序 DP问题：优化问题的四个步骤，0-1背包 Greedy(贪心算法):分数背包，0-1背包，霍夫曼编码 图的算法：3+1算法，具体是单源点最短路径（Dijkstra、Bellman-Ford），每对结点间最短路径（Floy算法），johnson算法（这个算法只要知道基本思想即可）（图的算法，3+1，单源最短路径：迪杰斯特拉，Bellman-Ford；每队节点间的最短路径：弗洛伊德算法johnson算法） 收索算法：回溯，N皇后问题，分支和边界算法 NP-complete：NP完全问题 智能收索(邻域收索)：基本思路，算法分析 算法设计：分治，动态规划，收索 四，考点分析 插入排序：插入排序的计算时间 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-表示法 主方法：（考计算题）提供了一种快速求解下述形式递归式的方法： T(n) = a T(n/b) + f(n) 其中a、b为常数，a ≥ 1 且 b 1 ，f(n) 为一渐近正函数 递推式的三种基本情况： 主定理思想： 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. 堆排序：具有n个元素的堆，其高度为： （1）MAX-HEAPIFY 调整堆以使其满足大顶堆的性质。O(log n) （2）BUILD-MAX-HEAP 基于无序数组构建大顶堆。Θ(n) （3）要完成排序，首先将数组转换成大顶堆，然后不断地取出根元素（最大元素），并利用MAX-HEAPIFY调整剩余元素。 Θ(n log n)，堆排序是原地排序(in place). 不稳定. 堆排序伪代码： 优先级队列：（1）优先级队列: 一种包含若干元素集合S 的数据结构，每个元素关联一个称为关键字(key)的值。 有两种优先级队列：最大优先队列与最小优先队列。我们以如何实现最大优先队列为例来讲解，它基于大顶堆实现。 快速排序： （1）分治算法， 原地排序 (与插入排序类似，与归并排序不同)，非常实用 (需要精心实现)，-可认为是一个随机拉斯维加斯算法的实例，最坏情况下的计算时间: Θ(n2)， 平均计算时间: Θ(nlogn)，Θ(nlogn) 量级下的常数系数比较小 （2）要对n个元素的数组完成快排： --分: 将原数组围绕某划分元素 x 划分为两个子数组，使得前面子数组中元素≤x≤后面子数组中元素 --治: 递归对子数组进行排序 --合并: 不需任何工作. 时间复杂度：快排的最坏情况：输入数据是有序或逆序的，基于最小或最大元素进行划分，这样划分后的一侧总是没有元素导致 --T(n) = T(n - 1) + T(0) + Θ(n)