搜索
第二章算法效率分析基础2.5计算斐波那契数列的O(logn)算法：利用矩阵，当n=1时，[F(n-1),F(n);F(n),F(n+1)]=[0,1;1,1]^n其中的乘方运算使用霍纳法则第三章蛮力法凸包问题：链接任意两点，检查剩余的点是否都在连线的同侧。效率O(n^3)分配问题：n个任务分配给n个人，其中将第j个任务分配给第i个人的成本为C[i,j]，找出成本最小的分配方案。蛮力法：穷举n!种可能的方案。高效方法：匈牙利方法。第四章分治法主定理：对于T(n)=aT(n/b)+f(n),f(n)为Θ(n^d)如果ab^d,T(n)=Θ(n^d)如果a=b^d,T(n)=Θ(n^d*logn)如果ab^d,T(n)=Θ(n^(loga/logb))大整数乘法：a=a1a0,b=b1b0,其中a和b都是n位整数，低n/2位为a0,b0,高位为a1,b1需要三次n/2位的乘法即可完成c=a*b=c2*10^2n+c1*10^n+c0其中c2=a1*b1,c0=a0*b0,c1=(a1+a0)*(b1+b0)-(c2+c0)T(n)=n^(log3/log2)最近点对问题：找到平面上n个点中的最近距离。先画一条竖线，将所有的点分成左右两半，找到两部分的最近距离d1,d2,然后考察竖线附近的点。凸包问题的快包算法（类似于快速排序）：首先过最左边的点P1和最右边的点Pn，将平面分成上下两部分。然后考察上半个平面：找到距离直线P1Pn距离最远的点Pmax,那么Pmax一定是凸包的顶点；三角形P1PmaxPn内部的点一定不是凸包的顶点。然后只需分别考虑两侧的顶点即可。平均效率O(n*logn)。由于三角形内部的点无须考虑，甚至可以达到线性效率。最差情况O(n^2)：剩下的点全都在同一侧。三角形面积的计算：三角形(x1,y1),(x2,y2),(x3,y3)的面积等于下面这个行列式的值的1/2[x1,y1,1;x2,y2,1;x3,y3,1]=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3第五章减治法插入排序：最差情况需要做(n-1)*n/2次比较，但是平均只需n^2/2次比较，因此胜过选择排序和冒泡排序。插入排序有一种扩展算法，叫做Shell排序。拓扑排序：算法1，通过深度优先搜索，将出栈顺序反过来即得到一个解。算法2，先找到一个只有出度没有入度的点，将这个点以及相关的边删除，重复此过程。生成排列：依次生成从1到n的所有排列。假设已经得到了n-1的所有排列，那么依次取出n-1的每一个排列，将n插入每一个位置。按这样的顺序插入更好：对于取出的第一个(n-1)排列，从右到左插入；第二个排列从左到右插入；第三个再从右到左...例子：依次生成1到3的所有排列开始：1从右到左将2插入1：12,21从右到左将3插入12：123,132,312从左到右将3插入21：321，231，213依这种次序生成的排列满足最小变化要求：得到的两个相邻的排列的差别仅在于交换两个相邻的位置。生成排列：生成n的所有排列。可不可以不通过（n-1）排列，而直接生成n的排列，并满足最小变化要求呢？通过Jhonson-Trotter算法：对每个元素赋予一个向左或向右的箭头。如果元素k指向一个相邻的较小的元素，则称k为移动的#JhonsonTrotter(n)#初始序列1...n,所有箭头均向左#while存在一个移动元素kdo#求最大的移动元素k#把k和它指向的元素互换#调转所有大于k的元素的方向#输出新的排列此算法和上面的算法生成的顺序是一样的，且都不是按字典序。生成子集：利用二进制。可否按这个顺序生成二进制串：使得两个相邻的二进制串只相差一个比特位。（也就是在子集里面要么增加了一个元素，要么删除了一个元素）。答案为“是”，通过二进制反射格雷码。俄式乘法：原理如下，如果n是偶数，那么n*m=(n/2)*(2m),否则n*m=(n-1)/2*2m+m代码#对整数a和b相乘#result=0#while(a0){#if(a%2==1){result+=b;}#a/=2;#b*=2;#}特点：只涉及折半、加倍和相加操作，效率非常高。约瑟夫问题：n个人围成一圈，并且从1到n编上号码，从1号开始，每隔一个杀掉一个，问最后剩下几号？记幸存者的号码为J(n)，那么当n为偶数时，也就是n=2k，J(2k)=2J(k)-1当n=2k+1时J(2k+1)=2J(k)+1把n表示为二进制形式，并且做一次向左的循环移位，得到结果就是幸存者编号。比如n=6时，二进制为110，移位后得到101，也就是5号为幸存者。具体推导过程见《具体数学》插值查找：对有序数组进行查找。把数组看成是线性递增的，那么便可以直接定位到目标值附近。一般情况下，比折半查找要快。拈游戏：两人轮流取走桌面上的棋子，每次取1到m颗，取到最后一颗的获胜。升级版：桌面上有I堆棋子，棋子数分别为n1,n2,...ni。玩家每次可以从任意一堆棋子中取走任意数量的棋子。取走最后一颗棋子的人获胜。对于I＝2的情况非常简单。（略）解法：将n1,n2,...ni表示为二进制的形式，b1,b2...bi，计算它们的二进制数位和，也就是对每一位分别求和并忽略进位。当且仅当二进制数位和中包含至少一个1时，先手获胜。先走的玩家只需保证剩下的棋子二进制数位和只包含0即可。《WinningWaysforyourMathematicalPlays》这本书包含了各种数学游戏的解法。第6章变治法预排序：用于下列场景，检验数组中元素的唯一性，查找数组中出现次数最多的元素，等等高斯消去法：将矩阵变成一个上三角阵，然后从最后一个方程开始，反向替换得到原方程的解。为了减少舍入误差，每次选取第i列系数绝对值最大的行，并且与当前行交换。LU分解：高斯消去法得到的上三角阵为U，在消去过程中行的乘数构成了下三角阵L（假设不存在行交换的情况下）。比如，在消去第i列的时候，把第i行乘以a加到第j行上，那么U[j][i]=-a。如果存在行交换的话，那么L也要做相应的交换。可以证明A=LU那么方程组Ax=b就等价于LUx=b。假设y=Ux，那么Ly=b，因为L是下三角阵，所以容易求出y。Ux=y，所以也容易求出x。优点：只需做一次LU分解，然后对所有的b都可以求解。计算矩阵的逆：AX=I假设逆矩阵的第j列为Xj,I的第j列为ej。那么原方程便等价于求n的方程组A*Xj=ej可通过LU分解来求。计算行列式：高斯消去法的每一步，要么改变行列式的符号，要么将行列式乘上一个常量，要么不变。最终得到一个上三角阵，三角阵的行列式等于对角元之积。所以容易推得原行列式的值。AVL树：是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左右子树的高度差，这个因子要么为0要么为1或-1。（注意：并不只是根节点满足这个特性，所有节点要都满足）将一个节点插入AVL树，可能导致失去平衡，某些节点的平衡因子变成了2或－2。通过旋转操作来回复平衡。旋转分为四种R（右旋），L（左旋），LR（先对节点r的左子树左旋，然后将以r为根的树右旋），RL。在插入节点后，先找到最靠近插入节点的不平衡节点，然后旋转以该节点为根的树。2-3树：节点分为两种，2节点－－包含1个元素和2个儿子，3节点－－包含2个元素和3个儿子，儿子可以为空。所有的叶子都必须在同一层。总是将新的键插入到叶子里，如果叶子中的键变成了3，那么将中间的键移至父节点，并且该叶子分裂成了两个节点。分裂过程可能一直向上进行。堆和堆排序：略霍纳法则：对多项式p(x)=an*x^n+a_(n-1)*x^(n-1)+...+a0进行求值。也可用来进行求幂运算。#Horner(p[0..n],x#r=p[n]//p[n]为x的n次项的系数#for(i=n-1;i=0;i--)#r=x*r+p[i]#returnr计算图中的路径数量：假设图的邻接矩阵为A，那么A^k中的元素A^k[i,j]表示了从顶点i到顶点j存在多少条长度为k的路径。第八章动态规划计算二项式系数：C(n,k)=C(n-1,k-1)+C(n-1,k)。边界C(n,0)=C(n,n)=1Warshall算法：计算有向图的传递闭包，也就是任意两个顶点之间是否可达。R(i,j,k)表示i和j之间是否连通，其中中间节点在集合{1,2,...k}里面那么R(i,j,k)=R(i,j,k-1)||(R(i,k,k-1)&&R(k,j,k-1))Floyd算法：计算每对顶点之间的最短路径。思路同上，只不过把布尔值换成最短距离而已。最优二叉查找树：给定每个key出现的概率，构造一棵二叉查找树，使得平均比较次数最少。假设键值从小到大为a1,a2,...an,对应的概率分别为p1,p1,...pn。令C[i,j]表示由节点i到j构成的子树中的最少查找次数，那么树根k一定在i,i+1,...j中，并且两棵子树都是最优的。可以推知C[i,j]=min{C[i,k-1]+C[k+1,j]}+Σp[i,...j]背包问题：物品重w1,w2,...wn，价值v1,v2,...vn，背包承重W。令V[i,w]为前i个物品中，总重量不超过w的物品集的最大价值。这个物品集要么不包括i，要么包括i。那么V[i,w]=max{V[i-1,w],vi+V[i-1,w-wi]}如果w-wi0，那么就只有V[i,w]=V[i-1,w]时间和空间效率都是O(nW)，求最优解的具体组成的效率为O(n+W)