Chapter01.BigOO()即<=洛必达法则一边有分母，一边无分母的，可以两边都先乘分母再比较，或再用洛必达法则例：logn!=Θ(lognn)因为(n/2)log(n/2)=log(n/2)n/2<=logn!<=lognn=nlogn任何指数形式>任何多项式形式任何多项式形式>任何对数形式Chapter11.复杂度计算Mod运算等于一个除法运算的复杂度一般，计算复杂度，先看循环次数（注意以比特位n计算时，logN=n），再看循环内复杂度最高的那个运算n位长数作加减运算，为O(n)，作乘除法运算为O(n2)乘2，除2，相当于移位，是常数时间运算2.计算modmod和加减乘除运算规则相同，也有交换律、结合律、分配率、替换率例如，21390mod31=(25)xmod31=(32)xmod31=(1)xmod31=1若ax=1modN，则a和x互为modN下的模倒数，有模倒数的充要条件是a和N互质例：求20mod79的模倒数用辗转相除法，每个式子标记3个数（除系数外都标记）共产党（20，79）79=3*20+19共产党（19，20）20=1*19+1共产党（1，19）19=1*19+0共产党（0，1）1=1-0再逆代回去（逆代的每一步都找对应共产党时作标记的数，用余数代换，用被除数合并）1=1-（19-1*19）代换0然后合并1=20*1-19=20*（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.分而治之Divideandconquer:T(n)=aT(n/b)+O(nd)在递归中的每一层，将处理问题分为a个子问题（即子问题个数是上一级的a倍），而每个子问题处理时的对象（函数的输入）被分为b份（即对象大小为上一级的1/b），而每一步的复杂度为O(nd)2.Mastertheorem:T(n)=O(nd)d>logbaT(n)=O(ndlogn)d=logbaT(n)=O(nlogba)d<logbaMerge算法处理n个元素merge的复杂度为O(n)T(n/2)是执行了logn层递归，T(n/b)是执行了logbn层递归Chapter31.DFS（有向图无向图都适用）Explore算法只对起始点可达的点visit，包括previsit和postvisit标记Explore(v)会生成以v为根的子搜索树DFS算法是对G中所有的点用exploreforallvinV:ifnotvisited(v)thenexplore(G,v)DFS算法复杂度为O(|E|+|V|)因为DFS中，previsit(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算法后，对postnumber降序排序，postnumber越小越靠后DAG图线性化方法二：从图中找一个源，删除它，不断重复该过程直至图为空3.SCC强连通子图u和v连通指从u->v有路径，同时从v->u也有路径可达对无向图，连通子图个数就是其DFS算法中的搜索树的棵树无向图作出连通子图的方法：在DFS算法中加个数组ccnum[v]赋初值为cc（cc=0），DFS过程中每调用一次explore则cc++，最后cc值为连通子图个数，有相同ccnum值的v即为一个连通子图对有向图中所有互相连通的节点归为一个个强连通子图后（一个子图视为一个节点），有向图成为一个DAG图，该DAG图中的源称为源强连通子图，其汇称为汇强连通子图Lemma1：对一个汇SCC内任意一节点用explore算法，可以刚好visit该子图内所有点（因为互相连通，且因为是汇，故不会visit该SCC以外的点）Lemma2：有向图的postnumber最大值必存在于其源强连通子图中Lemma3：若有一条边是从强连通子图C通向另一个强连通子图C’，则C中Maxpostnumber>C’中Maxpostnumber，所以有向图可以通过对其每个强连通子图的Maxpostnumber降序排序来线性化有向图作出其强连通子图的方法（线性时间）：（1）在其反向图G’上用DFS算法（G’上的源SCC就是G上的汇SCC，为了应用Lemma1，因为只有汇SCC才能一次explore找出该SCC所有点）（2）用无向图作连通子图的算法处理G，且DFS过程中对每个节点以其在(1)中的postnumber降序顺序来处理（应用Lemma2和Lemma3）Chapter41.BFS深度优先搜索（有向图无向图都适用）bfs(G,s)从s点出发f...