《算法分析知识汇总》由会员分享，可在线阅读，更多相关《算法分析知识汇总（6页珍藏版）》请在金锄头文库上搜索。
1、Chapter 01. Big OO() 即 = 洛必达法则一边有分母，一边无分母的，可以两边都先乘分母再比较，或再用洛必达法则例：log n! =(lognn)因为(n/2)log(n/2)=log(n/2)n/2=logn! 任何多项式形式任何多项式形式 任何对数形式Chapter11.复杂度计算Mod运算等于一个除法运算的复杂度一般，计算复杂度，先看循环次数（注意以比特位n计算时，logN=n），再看循环内复杂度最高的那个运算n位长数作加减运算，为O(n)，作乘除法运算为O(n2)乘2，除2，相当于移位，是常数时间运算2.计算modmod和加减乘除运算规则相同，也有交换律、结合律、分配率
2、、替换率例如，21390 mod 31 = (25)x mod 31 = (32)x mod 31 = (1)x mod 31 = 1若ax=1 mod N，则 a和x互为mod N下的模倒数，有模倒数的充要条件是a和N互质例：求20 mod 79的模倒数用辗转相除法，每个式子标记3个数（除系数外都标记）gcd（20，79） 79=3*20+19gcd（19，20） 20=1*19+1gcd（1，19） 19=1*19+0gcd（0，1） 1=1-0再逆代回去（逆代的每一步都找对应gcd时作标记的数，用余数代换，用被除数合并）1=1-（19-1*19） 代换0然后合并1 =20*1-19 =2
3、0*（20-1*19）-19 代换1然后合并19 =20*20-21*19 =20*20-21*（79-3*20）代换19然后合并20 =83*20-21*79故模倒数为83，又因模倒数必须在1至N之间，则为83-79=4Chapter21.分而治之 Divide and conquer: T(n)=aT(n/b)+O(nd)在递归中的每一层，将处理问题分为a个子问题（即子问题个数是上一级的a倍），而每个子问题处理时的对象（函数的输入）被分为b份（即对象大小为上一级的1/b），而每一步的复杂度为O(nd)2.Master theorem: T(n)= O(nd) dlogbaT(n)= O(n
4、dlogn) d= logbaT(n)= O(nlogba) dlogbaMerge算法处理n个元素merge的复杂度为O(n)T(n/2)是执行了logn层递归，T(n/b)是执行了logbn层递归Chapter31.DFS（有向图无向图都适用）Explore算法只对起始点可达的点visit，包括previsit和postvisit标记Explore(v)会生成以v为根的子搜索树DFS算法是对G中所有的点用explorefor all v in V: if not visited(v) then explore(G ,v)DFS算法复杂度为O(|E|+|V|)因为DFS中，previsit(
5、v)时，对v为根的子搜索树为陌生的，而postvisit(v)时则对子树已完全熟悉，所以若u和v是祖先-孩子关系，则必有pre(u)，post(u)包含pre(v)，post(v)，否则u，v完全不相交，不可能出现部分相交的关系，如pre(u) pre(v)post(u)post(v)2.DAG有向无环图对有向图用DFS算法，若其生成的搜索树中有回边该图存在环DAG必有至少一个源（入度为0），和至少一个汇（出度为0），必可以线性化凡DAG图问题，必先线性化DAG图线性化方法一：用DFS算法后，对post number降序排序，post number越小越靠后DAG图线性化方法二：从图中找一个源
6、，删除它，不断重复该过程直至图为空3.SCC强连通子图u和v连通指从u-v有路径，同时从v-u也有路径可达对无向图，连通子图个数就是其DFS算法中的搜索树的棵树无向图作出连通子图的方法：在DFS算法中加个数组ccnumv赋初值为cc（cc=0），DFS过程中每调用一次explore则cc+，最后cc值为连通子图个数，有相同ccnum值的v即为一个连通子图对有向图中所有互相连通的节点归为一个个强连通子图后（一个子图视为一个节点），有向图成为一个DAG图，该DAG图中的源称为源强连通子图，其汇称为汇强连通子图Lemma1：对一个汇SCC内任意一节点用explore算法，可以刚好visit该子图内所
7、有点（因为互相连通，且因为是汇，故不会visit该SCC以外的点）Lemma2：有向图的post number最大值必存在于其源强连通子图中Lemma3：若有一条边是从强连通子图C通向另一个强连通子图C，则C中Max post number C中Max post number，所以有向图可以通过对其每个强连通子图的Max post number降序排序来线性化有向图作出其强连通子图的方法（线性时间）：（1） 在其反向图G上用DFS算法（G上的源SCC就是G上的汇SCC，为了应用Lemma1，因为只有汇SCC才能一次explore找出该SCC所有点）（2） 用无向图作连通子图的算法处理G，且DF
8、S过程中对每个节点以其在(1)中的post number降序顺序来处理（应用Lemma2和Lemma3）Chapter41.BFS 深度优先搜索（有向图无向图都适用）bfs(G, s) 从s点出发for all u in V dodist(u) = ; 初始距离都赋为无穷dists = 0; 访问s，距离设为0Q = s 设一个队列Q，初始只有s点while Q is not empty do 队列为空是终止条件u=Eject(Q); 把u移出队列（loop第一次的时候u即为s）for all edge (u, v) in E do 对所有u能到达的点if dist(v) = then 若未访
9、问过则Inject(Q, v); 加入队列distv = distu + 1; 距离为u+1每次循环会先把该层搜索到的点都加入Q，下一层循环时再eject，并从该点出发再访问其可到达的点，下一层的点距离会多1BFS复杂度为O(|E|+|V|)注：BFS只考虑distance from s，所以不会再去搜索s不可达的点，这和DFS是不同的。BFS视所有边长度相同（为1），故只能找到边长都为1的图中的最短路径2.最短路径算法（有向图无向图都适用）当边长度不为1时，利用插入dummy点的思想（如边长为10，相当于该边上插入9个dummy点后，化为边长为1），可以用BFS算法计算最短路径，但如果边长很
10、长，则算法效率太低。于是再加上set alarm的方法和引入特殊数据结构priority queue，有了Dijkstra算法Dijkstra算法：从s点出发作BFS算法，每探索1层，把该层可达的点的距离值更新，然后选距离数组中值最小的点，从该点出发再探索下一层，并更新距离数组注：loop中每次被选中的距离值最小的点会被移出队列，故表示它的值已确定下来，之后不会再被更新，队列为空则算法终止Dijkstra复杂度：当用二叉堆形式的数组时，为O(|V| + |E|) log |V|)二叉堆：是完全二叉树（第k层未满时，不会有第k+1层，左分支未填时不会有右分支），该数组中，节点j的parent为j
11、/2取下界，j的children为2j和2j+13.有负边的图最短路径算法Dijkstra不适用Bellman-Ford算法：repeat V-1 times： 循环V-1次 for all e in E 检查所有边，更新其端点的dist值 update(e)Bellman-Ford复杂度为O(|V|E|)Bellman-Ford可用于检定图中是否有负环，只要在V-1次迭代后再多迭代一次，如果仍有dist数组的更新，则图中必有负环4.DAG图最短路径算法（正边负边都适用）先线性化DAG图，然后for each u in V, in linearized order for all edges
12、(u, v) in E 对所有u相连的e作update(e) update(u, v)特别地，把DAG图中所有边*(-1)后，可以用该算法求最长路径Chapter51.MST最小生成树有最小的总权数的树是MST（不唯一）Lemma1：移除环中的一条边，不会使图disconnectLemma2：n节点的树有n-1条边Lemma3：任何连接的无向图G（V, E），若有E=V-1，则G必为树Lemma4：无向图为树任意两个节点之间有唯一路径Kruskals MST算法：从空图开始，每次选一条不会使图产生环的权重最小的边（贪婪算法每次作最符合当前利益的选择）每一次如何高效地挑选不会使图产生环的权重最小
13、的边？2.割定理：设边集X为G的某个最小生成树T的子集，任意将G切割成集合S和V-S，使X里没有边横跨S和V-S，则将e加到X中形成的新集合X也是某个MST的子集，这里e是横跨S与V-S的所有边里权重最小的边。（即选S时，把X中所有边都包含进去即可）Kruskals MST算法实现：for all u in V domakeset (u); 初始用makeset建立V个分离集（每个顶点为一个集合）X = ;Sort the edges E by weight;for all e=u, v in E in increasing order of weight doif find (u) != f
14、ind (v) then add e=u, v to X;union (u, v)这里find是用来找tree的根，find(u) != find (v)表示u所在集合的树根与v所在集合的树根不同，也就是说u和v不在一个集合内union是用来合并两个集合，union (u, v)合并u所在集合和v所在集合，并选择树高较大的集合的根节点作为合并后的根节点（只有相同树高的两颗树合并，总树高才会加1，其它情况合并，树高都不变）Kruskal算法生成的树有如下性质：Lemma1：非根节点的rank根节点的rank（rank为在树中的高度，从叶子往上算）Lemma2：rank为k的树有至少2k个节点（k
15、从0开始）Lemma3：若整个树有n个节点，则rank为k的节点至多有n/2k个，即树最大高度为logn所以Kruskal算法复杂度为maxO(|E|), O(|V|log|V|)Chapter 61.动态规划为解决问题，先定义一组子问题，而原问题的最优解由子问题的最优解构成，逐步追溯子问题至更小的子问题，直至到最简的形式（某个已知的或显而易见的解）动态规划与分而治之的差别：都是分解问题，但分治每次将问题分解得更小（通常至少是每次分解为一半），而动态规划只是分解为稍稍小一点的问题（通常只是f(n)分解至f(n-1)）。所以动态规划每次是基于已得到的子问题的最优解而进行的，不会像分治那样每次再去计算一遍子问题，那样的话会变成指数级运算时间。（也就是说，如果子问题出现大量重叠，则用动态规划将非常有效）复杂度：
