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

1算法导论复习——常见算法思想PPT2-1：1.堆排序（选择类排序，不稳定）（1）初始化操作：将R[1..n]构造为初始堆；（2）每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。时间复杂度是：O（nlgn）2.归并排序归并排序采用分治法思想的稳定的排序。算法思想是先使每个子序列有序，再使子序列段间有序。第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。时间复杂度是：O（nlgn）3.快速排序（交换类排序，不稳定）（1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小；（2）然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度是：O（nlgn）。4.分治法实现大数相乘将a，b写成前一半数字和后一半数字相加的形式，例如若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四项这样就很容易递归的来求a*b，如果你嫌分解后的数还太大，就可以继续分解。（你可以自己规定在何时结束递归）时间复杂度是：O（nlgn）参考资料见：=kkSSG6aAlxeI7qlflvPWBrWPbpAeNtoohJvwk9ARQ3TwTkIx3_Fiwlt-5HLhrNUxg1C-i0Tus9oo_cCLiINr2CHiN1mgsidH3gX5rsY6Nuu5.分治法求最近点对步骤一：找一条中垂线m(坐位S集合x坐标的中位数)把n个元素分成左右两部分元素，步骤二：递归查找两边点集的的最短距离d1,d2，然后取两者中的最小者记为d；2步骤三：在中线两边分别取d的距离，记录该距离范围内点的个数，中线左边有L个元素，右边有R个元素，分别将两边的点按y坐标升序排列，在左边集合中每一个点，找右边集合的点，找到与之距离小于d的点，更新最短距离，直到循环结束，即可求出最短距离。时间复杂度是：O（nlgn）6.格雷厄姆Graham扫描法求凸包基本思想：通过设置一个关于候选点的堆栈s来解决凸包问题。操作：输入集合Q中的每一个点都被压入栈一次，非CH（Q）(表示Q的凸包)中的顶点的点最终将被弹出堆栈，当算法终止时，堆栈S中仅包含CH(Q)中的顶点，其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。具体步骤如下：（1）设P0是Q中Y坐标最小的点，如果有多个这样的点则取最左边的点作为P0；（2）设P1,P2,……,Pm是Q中剩余的点，对其按逆时针方向相对P0的极角进行排序，如果有数个点有相同的极角，则去掉其余的点，只留下一个与P0距离最远的那个点；（3）PUSH(p0,S)（4）PUSH(p1,S)（6）PUSH(p3,S)（7）fori←3tom{while由点NEXT-TOP-TOP（S），TOP（S）和Pi所形成的角形成一次非左转doPOP(S)PUSH(pi,S)}（8）returnS时间复杂度是：O（nlgn）注：Jarvis步进法更加容易理解，见算法导论中文版P609。7.D&Cfor2DmaximaFindingProblem（1）如果点集S只包含一个点，这直接输出该点。否则找一条中垂线m(坐位S集合x坐标的中位数)把n个元素分成左右两部分个数相等的元素，分别为Sl和Sr。（2）递归查找两边点集的的最大点；（3）将获得的所有最大点按y值排序，并查找出Sl中y值小于Sr中最大点的y值的最大点，并将其排除；（4）最终获得所有的点集S的所有maximalpoint。时间复杂度是：O（nlgn）Homework：VoronoiDiagramPPT2-2：8.DepthFirstSearch(DFS)深度优先搜索算法也叫回溯法，其基本策略是：尽可能深的深的搜索某一分支。从源节点开始发现有一节点v，如果v还有未探测到的边，就沿此边继续探测下去，当节点v的所有边都被探测过，搜索过程将回溯到最初发现v点的源节点。这一过程一直进行到已发现从3源节点可达的所有节点为止。这显然是一个递归过程。伪代码（使用栈实现），递归实现：longDFS(图g，结点v0){//图深度优先遍历递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数intnNodes;//寄存访问到的结点数目访问v0;为v0置已访问标志;nNodes=1;求出v0的第1个可达邻接点v;while(v存在){if(v未被访问过)nNodes=nNodes+DFS(g,v);求出v0的下个可达邻接点v;}returnnNodes;}非递归实现（借用栈实现）：longDFS_NR(图g，结点v0){//图深度优先遍历非递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数intnNodes;//寄存访问到的结点数目访问v0;为v0置已访问标志;v0进栈S；nNodes=1;//求出v0的第1个可达邻接点v;while(栈S不空){v=栈S顶部元素；求v的下个未访问过的出点i；访问i;为i置已访问标志;i进栈S；nNodes++;if(v已无未被访问过的出点)出栈；}returnnNodes;}9.BFS（BreadthFirstSearch）宽度优先搜索从初始结点开始，应用产生式生成第一层结点，检查目标结点是否在这些后继结点中，4若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。伪代码（使用队列实现）：longBFS(图g,结点v0）{//在图g中从v0出发按广度优先遍历方式遍历g，返回遍历到的结点数目longnNodes=0;初始化队Q;v0入Q;while(Q不空){队Q头元素出队并送v;访问v;置v0为已访问标志;nNodes++;//对已访问元素计数求出v的第一个可达邻接点w;while(w存在){if(w尚未被访问过){w入Q;}求v的下个可达邻接点w;}returnnNodes;}}两个算法的时间复杂度都是O（V+E）。10.拓扑排序（TopologicalSorting）一个有向图能被拓扑排序的充要条件就是它是一个有向无环图(DAG：DirectedAcyclicGraph)。拓扑排序就是一个广度优先搜索。拓扑排序的方法如下:(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.参考资料：字典序法生成全排列（permutation）设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn1.从右向左找，找到第一个比下一个元素还小的地方，记下位置，标注为左元素。2.从右向左找，找到第一个比左元素大的元素，也是左元素右边比左元素大的数中最小的数，5记下位置，标注为右元素。3.交换左元素和右元素。4.不管现在左元素位置上放的是谁，将左元素右边的序列逆序。5.这样就得到了一个新数了。6.可以继续重复1-5，来继续得到下一个排列。7.如果再也找不到一个比下一个元素还小的地方，那么意味着这个序列已经降序了，排列完成了，那就结束吧。时间复杂度：O(n!)参考资料：关节点（ArticulationPoint）见homework。13.约瑟夫问题（JosephusProblem）设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。Josephus问题是：对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。解决思想：循环链表表示1建立循环单链表2寻找第s个结点，输出并删除第m个节点。14.二查搜索树BST（BinarySearchTree）PART2-3:（Transform&Conquer）15.霍纳法则（HornerRule）霍纳法则出现的原因：为多项式求值提供了一个高效的方法。用来简化朴素多项式的求值，在中国叫秦九韶算法。朴素多项式可以简化为：举个例子，多项式变换如下：pseudocode:其中P[n]是多项式的系数组成的数组，616.平衡二叉树AVL(BalancedBinaryTree)17.红黑树R-B树参考链接：树每个节点最多包含两个关键子，所有叶子节点在树的同一层，因此树总是高度平衡的。19.堆Heap20.树堆Treap见homework，有可能考代码！21.优先队列PriorityQueue重点:优先级队列，是要看优先级的，谁的优先级更高，谁就先得到权限。不分排队的顺序!利用堆可以实现优先队列！21.迷宫问题MazeProblem使用DFS或者BFS遍历搜索出口！PART2-422.计数排序CountingSorting计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。伪代码：A待排序数组，B排序后的数组，k待排序中最大的数23.字符串匹配算法HorspoolAlgorithmsHorspool算法是对Boyer-Moore算法的简化。其基本思想（后缀匹配法）：模式串是需要匹配的串，主串是在其中查找模式串的字符串，匹配窗口是模式串从左往右移动，在主串中需要比对的字符形成的窗口。模式串是从左往右移动，字符比对是从匹配窗口的右边往左。7horspool算法将主串中匹配窗口的最后一个字符跟模式串中的最后一个字符比较。如果相等，继续从后向前对主串和模式串进行比较，直到完全相等或者在某个字符处不匹配为止（如下图中的α与σ失配）。如果不匹配，则根据主串匹配窗口中的最后一个字符β在模式串中的从右往左下一个出现位置，将窗口向右移动与之对齐。为了实现模式串的移动，必须先记录模式串中每一个字符（不包括最后一个字符）在模式中距离最右边的距离，如若出现相同字符的距离不同，取最短的距离：时间复杂度：假设主串的长度为n,模式串的长度为m，那么Horspool算法最坏情况下的时间复杂度是O(mn)，但平均情况下它的时间复杂度是O(n)。参考资料：字符串匹配算法BM：Boyer-Moore算法思想（后缀匹配法）：Boyer-Moore算法是一种基于后缀匹配的模式串匹配算法，后缀匹配就是模式串从右到左开始比较，但模式串的移动还是从左到右的。字符串匹配的关键就是模式串的