算法考试复习要点

算法考试复习提纲一、算法的基础知识1、算法的基本概念算法是由若干条指令组成的有穷序列，具有以下5个特征：确定性：每条指令都是明确的、无二义的能行性：每条指令都必须是能够执行的输入：允许有0个或多个输入量，取自特定的集合输出：产生一个或多个输出，它（们）与输入量之间存在着某种特定的关系有穷性：每一条指令执行的次数都是有穷的2、衡量算法好坏的标准最初，用所需要的计算时间来衡量一个算法的好坏，但不同的机器相互之间无法比较，需要用独立于具体计算机的客观衡量标准，包括：问题的规模基本运算算法的计算量函数3、渐近符号的概念和内涵符号O：对于存在大于0的常数c和非负的整数n0，以及足够大的n，对于所有的n≥n0来说，有t(n)≤cg(n)，我们说函数t(n)包含在O(g(n))中，记作t(n)∈O(g(n))。（上界）符号Ω：对于存在大于0的常数c和非负的整数n0，以及足够大的n，对于所有的n≥n0来说，有t(n)≥cg(n)，我们说函数t(n)包含在Ω(g(n))中，记作t(n)∈Ω(g(n))。（下界）符号Θ：对于存在大于0的常数c1、c2和非负的整数n0，以及足够大的n，对于所有的n≥n0来说，有c2g(n)≤t(n)≤1g(n)，我们说函数t(n)包含在Θ(g(n))中，记作t(n)∈Θ(g(n))。（上下界，即确界）换言之，一个算法的渐进时间由算法的多项式时间中次数最高的那一项决定。二、分治法1、分治法的基本概念把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。2、分治法适合求解问题的特点问题的规模缩小到一定程度就可以容易地解决问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质基于子问题的解可以合并为原问题的解问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3、分治法求解的一般过程。分解（Divide）：将原问题分解为子问题解决（Conquer）：求解子问题合并（Combine）：组合子问题的解得到原问题的解4、针对以下递归式，使用主方法给出渐近界（1）T(n)=9T(n/3)+n解：a=9，b=3，f(n)=n。nlogba=n2，取0ε1，则有，f(n)=O(n2-ε)=O（nlogba-ε），满足主定理情况一，所以，T(n)=Θ(logba)=Θ(n2)（2）T(n)=9T(n/3)+n^2解：a=9，b=3，f(n)=n2。nlogba=n2，则有，f(n)=O(n2)=O（nlogba），满足主定理情况二，所以，T(n)=Θ(logba*lbn)=Θ(n2*lbn)。（3）T(n)=9T(n/3)+n^3解：a=9，b=3，f(n)=n3。nlogba=n2，取0ε1，则有，f(n)=Ω(n2+ε)=Ω（nlogba+ε），满足主定理情况三，同时，af(n/b)=9*f(n/3)=9*(n/3)3=1/3*n3=1/3*f(n)，取1/3=c，即满足af(n/b)=cf(n)，所以T(n)=Θ(f(n))=Θ(n3)5、快速排序快速排序算法，对数组A[p..r]进行排序分解：数组A[p..r]被划分为子数组A[p..q-1]和A[q+1..r]，A[p..q-1]中的每个元素都小于等于A[q]，A[q+1..r]中的每个元素都大于等于A[q]，q在划分时确定解决：通过递归调用快速排序算法，对子数组A[q+1..r]和A[p..q-1]进行排序合并：由于子数组的排序为原地排序，解的合并不需要操作，整个数组已经排好序QUICKSORT(A,p,r)ifprthenq=PARTITIION(A,p,r)QUICKSORT(A,p,q-1)QUICKSORT(A,q+1,r)QUICKSORT(A,1,length[A])PARTITION(A,p,r)x←A[r]i←p-1forj←ptor-1doifA[j]≤xtheni←i+1exchangeA[i]↔A[j]exchangeA[i+1]↔A[r]returni+1最坏情况时间复杂度Θ(n2)平均情况时间复杂度Θ(nlgn)例：一趟划分过程中的数组的演化A[0]A[1]A[2]A[3]A[4]A[5]A[6]49386597761327取key=49，初始i=0,j=6；第一次：j--=5；27,38,65,97,76,13,49；第二次：i++=1；27,38,49,97,76,13,65；第三次：j--=4；27,38,13,97,76,49,65；第四次：i++=2；27,38,13,49,76,97,65；此时，j--=3=i++；OVER。故一趟快速排序后的序列为：27,38,13,49,76,97,65三、动态规划1、动态规划方法适合求解问题的特点若一个问题可以分解为若干个高度重复的子问题，且问题也具有最优子结构性质，就可以用动态规划法求解具体方式：可以递推的方式逐层计算最优值并记录必要的信息，最后根据记录的信息构造最优解与分治法类似，也是将问题分解为规模逐渐减小的同类型的子问题与分治法不同，分解所得的子问题很多都是重复的动态规划方法总体思想是：保存已解决的子问题的答案，在需要时使用，从而避免大量重复计算2、矩阵链乘问题1）找出最优解的性质，刻画其特征结构对于矩阵连乘问题，最优解就是找到一种计算顺序，使得计算次数最少。令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。将矩阵连乘积简记为A[i:j]，这里i=j.假设这个最优解在第k处断开，i=kj，则A[i:j]是最优的，那么A[i,k]和A[k+1:j]也是相应矩阵连乘的最优解。可以用反证法证明之。这就是最优子结构，也是用动态规划法解题的重要特征之一。2）建立递归关系递归式：用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。3）用动态规划算法解此问题可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。其他例子：如LCS问题：1）找出最优解的性质，刻画其特征结构设序列X=x1,x2,…,xm和Y=y1,y2,…,yn的一个最长公共子序列Z=z1,z2,…,zk，则：若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。2）建立递归关系3）用动态规划算法解此问题利用以上的递归式，很容易就能写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。四、随机算法1、基本概念随机算法适合的问题特点：有不少问题，目前只有效率很差的确定性算法求解，但用随机算法求解，可以很快的获得相当可信的结果，此类问题即适合使用随机算法求解。如RamdomSampling问题、素数测试、主元素问题等。随机算法可分为：LasVegas算法在少数应用中，可能出现求不出解的情况。但一旦找到一个解，这个解一定是正确的。在求不出解时，需再次调用算法进行计算，直到获得解为止。对于此类算法，主要是分析算法的时间复杂度的期望值，以及调用一次产生失败（求不出解）的概率MonteCarlo算法通常不能保证计算出来的结果总是正确的，一般只能断定所给解的正确性不小于p（1/2＜p＜1）通过算法的反复执行（即以增大算法的执行时间为代价），能够使发生错误的概率小到可以忽略的程度。由于每次执行的算法是独立的，故k次执行均发生错误的概率为(1-p)k对于判定问题（回答只能是“Yes”或“No”）带双错的（two-sidederror）：回答“Yes”或“No”都有可能错带单错的（one-sidederror）：只有一种回答可能错LasVegas算法可以看成是单错概率为0的MonteCarlo算法。随机算法对同一问题的实例求解两次可能得到完全不同的结果。2、主元素问题蒙特卡罗算法：五、回溯法和分枝限界法回溯法：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。如图的深度优先遍历分枝界限法：把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。如图的广度优先遍历1、0-1背包问题构造出问题的状态空间树以后，就可以从其根结点出发搜索解空间，即决定每个物品的取舍。为了使目标函数的值增加最快，可以优先选择价值最大的物品装入背包，然后是价值量次之的物品，……，直至背包装不下为止。但是，如果所选择的物品重量很大，使得背包载重量消耗速度太快，以至后续能装入背包的物品迅速减少，使得继续装入背包的物品在满足了约束方程的要求以后，无法达到目标函数的要求。因此，最好优先选择那些既使目标函数的值增加最快。又能使背包载重量消耗速度较慢的物品装入背包。为了达到这个目的，首先把所有物品按价值重量比的非增顺序排列，然后按照这个顺序进行搜索。在装包过程中，要尽量优先选择价值重量比较高的物品装入背包。表现在搜索过程中，就是要尽量沿着左子树结点前进。当不能继续前进时（假设该结点为T），就得到问题的一个部分解，并把搜索转移到右子树。估计由该部分解所能得到的最大价值，即结点T的上限。可以用贪婪算法处理剩余物品：将按照价值重量比非增顺序排列的剩余物品依次装入背包，至无法完全装入下一个物品时，就将该物品的一部分装满背包。这样就可以得到一个上限。如果该值为当前最优值：继续由右子树向下搜索，扩大部分解，直至找到可行解；保存可行解，并把可行解的值作为当前最优值，向上回溯，寻找其他可行解；若该值小于当前最优值：丢弃当前正在搜索的部分解，向上回溯。反复使用此方法，直至搜索完整个解空间。六、NP完全性1、P问题P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。NP是一个判定问题类，这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解，P事实上很直观，我们通常在编程中求解的问题大多都是P类问题。比如说排序，找最短路径等。2、NP问题然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。NP这个类事实上也很有趣，