目录算法概论 (1)序言 (1)第一章 (2)乘法 (2)除法 (2)两数的最大公因数 (2)扩展 (2)RSA (3)第二章：分治算法 (3)整数相乘的分治算法 (3)递推式 (3)2.3合并排序 (3)第三章图的分解 (4)3.2.1寻找从给定顶点出发的所有可达顶点 (4)3.2.2 深度优先搜索 (4)第四章 (4)4.2、广度优先搜索 (4)4.4.1、dijkstra最短路径算法 (5)4.6.1、含有负边 (5)Bellman-Ford算法 (6)4.7、有向无环图的最短路径 (6)第五章贪心算法 (6)5.1 最小生成树 (6)算法概论序言Fibonacci数列：死板的算法：function Fib1(n)If n=0:return 0If n=1:return 1Return fib1(n-1)+fib1(n-2)(递归，很多计算是重复的，不必要)合理的算法：functionFib2(n)If n=0:return 0Create an array f[0…n]f[0]=0,f[1]=1fori=2…n:f[i]=f[i-1] + f[i-2]return f[n](随时存储中间计算结果，之后直接调用)大O符号：若存在常数c>0，使得f(n)<=c*g(n)成立，则f=O(g)。
f增长的速度慢于g。
第一章乘法：functionMultiply(x,y)If y=0:return 0z=multiply(x,y/2)//向下取整If y is even: //even---偶数return 2zelse:return x+2z除法：functionDivide(x,y)If x=0: return (q,r)=(0,0)(q,r)=divide( x/2 ,y) //向下取整q=2*q,r=2*rif x is odd:r=r+1if r>=y :r=r-y,q=q+1return (q,r)p22两数的最大公因数：function Euclid(a,b)if b=0: return areturn Euclid(b,a mod b)扩展：function extended-Euclide(a,b)if b=0: return (1,0,a)(x1,y1,d)=extended-Euclide(b,a mod b)retrun (y1,x1-a/b*y1,d)RSA:(X^e)^d ==X mod Nd=e^-1 mod(p-1)(q-1)N=pq第二章：分治算法整数相乘的分治算法：function multiply(x,y)input:n-bit positive integers x and youtput:their productif n=1:return xyxl,xr=leftmost n/2_^ ,rightmost n/2_v bits of x // _^表示向上取整，_v表示向下取整yl,yr=leftmost n/2_^ ,rightmost n/2_v bits of yp1=multiply(xl,yl)p2=multiply(xr,yr)p3=multiply(xl+xr,yl+yr)return p1*p2+(p3-p1-p2)*2^(n/2)+p22.2递推式：T(n)={ O(nd):d>logba|| O(n d *log n) :d=log b a|| O(n^(log b a)): d<log b a}2.3合并排序function mergersort(a[1…n])if n>1:return merge(mergesort( a[1…n/2]), a[n/2+1…n]))else:return afunction merge(x[1…k], y[1…L] )if k=0: return y[1…L]if L=0: return x[1…k]if x[1]<=y[1]:return x[1]＆merge(x[2…k],y[1…L])else:return y[1]&merge( x[1…k], y[2…L] )第三章图的分解3.2.1寻找从给定顶点出发的所有可达顶点：procedure explore(G,v)input:G=(V,E) is a graph; v ∈Voutput:visited(u) is set to true for all nodes u reachable from vvisited(v)=trueprevisit(v)for each edge(v,u)∈E:if not visited(u):explore(u)postvisit(v)3.2.2 深度优先搜索：proceduredfs(G)for all v ∈V:visited(v)=falsefor all v∈V:if not visited(v):explore(v)线性化序列：对图深度优先搜索，取post的降序序列。
求强连通部件：1、在反转图上运行深度优先搜索，得到post值大的点v，运行explore(G,v)。
第四章：4.2、广度优先搜索bfs(G,s)算法简述：所有dist(u)设为无穷大；dist(s)=0;入队Q(s);while Q 不空：出队u：所有边u->v:if dist(v)=∞：入队v,dist(v)=dist(u)+1--------------procedurebfs(G,s)for all u∈V:dist(u)=∞dist(s)=0Q=[s] (queue containing just s,入队s,以dist值为key )while Q is not empty:u=eject(Q) //出队最小的keyfor all edges(u,v)∈E∶ifdist(v)=∞:inject(Q,v)dist(v)=dist(u)+14.4.1、dijkstra最短路径算法：（只适用于权值为正值）proceduredijkstra(G,l,s)input:Graph G=(V,E), directed or undirectedOutput:For all vertices u reachable from s,dist(u) is set to the distance from s to u.For all u∈V:Dist(u)=∞Prev(u)=nildist(s)=0H=makequeue(V) (using dist-values as keys)while H is not empty:u=deletemin(H)for all edges(u,v)∈E:ifdist(v)>dist(u)+l(u,v):dist(v)=dist(u)+l(u,v)prev(v)=udecreasekey(H,v) //更新队列4.6.1、含有负边：procedure update((u,v)∈E)dist(v)=min{ dist(v), dist(u)+l(u,v) }Bellman-Ford算法：procedure shortest-paths(G,l,s)for all u∈V:Dist(u)=∞Prev(u)=nildist(s)=0repeat |V|-1 times:for all e∈E:update(e)4.7、有向无环图的最短路径procedure dag-shortest-paths(G,l,s)for all u∈V:Dist(u)=∞Prev(u)=nildist(s)=0Linearize G //线性化for each u∈V,in linearized order:for all edges (u,v)∈E:update(u,v)第五章贪心算法5.1 最小生成树Kruskal:不断重复地选择未被选中的边中权重最轻且不会开成环的一条。
子函数：proceduremakeset(x)π(x)=x //π(x)意为x的父节点rank(x)=0function find(x) //找x的根节点while x≠π(x): x=π(x)return x或：function find(x)if x≠π(x): π(x)=find(π(x))returnπ(x)procedure union(x,y)rx=find(x)ry=find(y)ifrx=ry:returnif rank(rx)>rank(ry):π(ry)=rxelse:π(rx)=ryif rank(rx)=rank(ry):rank(ry)=rank(ry)+1Kruskal:procedurekruskal (G,w)for all u∈V:makeset (u)X={}sort the edges E by weightfor all edges {u,v}∈E ,in increasing order of weight:if find(u)≠find(v):add edge {u,v} to Xunion(u,v)prim算法：procedure prim(G,w)for all u∈V:cost(u)=∞prev(u)=nilpick any initial node u0cost(u0)=0H=makequeue(V) (priority queue,using cost-values as keys) while H is not empty:v=deletemin(H)for each {v,z}∈E:if cost(z)>w(v,z):cost(z)=w(v,z)prev(z)=vdecrease(H) //更新。