算法分析与设计常见算法思想

《算法分析与设计常见算法思想》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法导论复习——常见算法思想PPT2-1：1.堆排序（选择类排序，不稳定）（1）初始化操作：将R[1..n]构造为初始堆；（2）每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。时间复杂度是：O（nlgn）2.归并排序归并排序采用分治法思想的稳定的排序。算法思想是先使每个子序列有序，再使子序列段间有序。第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位

2、置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。时间复杂度是：O（nlgn）3.快速排序（交换类排序，不稳定）（1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小；（2）然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度是：O（nlgn）。4.分治法实现大数相乘将a，b写成前一

3、半数字和后一半数字相加的形式，例如若a = 5423678，那么a1 = 542，a0 = 3678（注意若不是偶数截取较小一半）  这样a和b相乘就可以写为：a * b = {  a1 * 10^(n1/2)   +  a0  }   *  {  b1 * 10^(n2/2)  +  b0 }  展开后整理得： a  *  b  =  a1*b1 * 10^[ (n1+n2)/2 ]   +  a1*b0 * 10^(n1/2)   +   a0*b1 * 10^(n2/2)  + a0*b0  四项 

4、 这样就很容易递归的来求a * b，如果你嫌分解后的数还太大，就可以继续分解。（你可以自己规定在何时结束递归）时间复杂度是：O（nlgn）参考资料见：http://wenku.baidu.com/link?url=kkSSG6aAlxeI7qlflvPWBrWPbpAeNtoohJvwk9ARQ3TwTkIx3_Fiwlt-5HLhrNUxg1C-i0Tus9oo_cCLiINr2CHiN1mgsidH3gX5rsY6Nuu5.分治法求最近点对步骤一：找一条中垂线m(坐位S集合x坐标的中位数)把n个元素分

5、成左右两部分元素，步骤二：递归查找两边点集的的最短距离d1,d2，然后取两者中的最小者记为d；15步骤三：在中线两边分别取d的距离，记录该距离范围内点的个数，中线左边有L个元素，右边有R个元素，分别将两边的点按y坐标升序排列，在左边集合中每一个点，找右边集合的点，找到与之距离小于d的点，更新最短距离，直到循环结束，即可求出最短距离。时间复杂度是：O（nlgn）1.格雷厄姆Graham扫描法求凸包基本思想：通过设置一个关于候选点的堆栈s来解决凸包问题。操作：输入集合Q中的每一个点都被压入栈一次，非CH（Q）

6、(表示Q的凸包)中的顶点的点最终将被弹出堆栈，当算法终止时，堆栈S中仅包含CH(Q)中的顶点，其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。具体步骤如下：（1）设P0是Q中Y坐标最小的点，如果有多个这样的点则取最左边的点作为P0；（2）设是Q中剩余的点，对其按逆时针方向相对P0的极角进行排序，如果有数个点有相同的极角，则去掉其余的点，只留下一个与P0距离最远的那个点；（3）PUSH(p0,S)（4）PUSH(p1,S)（6）PUSH(p3,S)（7）fori←3tom{wh

7、ile由点NEXT-TOP-TOP（S），TOP（S）和Pi所形成的角形成一次非左转doPOP(S)PUSH(pi,S)}（8）returnS时间复杂度是：O（nlgn）注：Jarvis步进法更加容易理解，见算法导论中文版P609。2.D&Cfor2DmaximaFindingProblem（1）如果点集S只包含一个点，这直接输出该点。否则找一条中垂线m(坐位S集合x坐标的中位数)把n个元素分成左右两部分个数相等的元素，分别为Sl和Sr。（2）递归查找两边点集的的最大点；（3）将获得的所有最大点按y值排序

8、，并查找出Sl中y值小于Sr中最大点的y值的最大点，并将其排除；（4）最终获得所有的点集S的所有maximalpoint。时间复杂度是：O（nlgn）Homework：VoronoiDiagramPPT2-2：3.DepthFirstSearch(DFS)深度优先搜索算法也叫回溯法，其基本策略是：尽可能深的深的搜索某一分支。从源节点开始发现有一节点v，如果v还有未探测到的边，就沿此边继续探测下去，当节点v的所有边都被探测过，搜