最近翻了下算法概论和算法导论，这里做点记录（按算导的目录来）。
第一部分
主要讲了算法的作用和刻画算法的方式（大O）。具体算法有分治发和随机算法。
分支法能解决在结构上递归的问题，即算法一次或多次递归地调用自身解决诺干子问题。主要步骤：
- 分解原问题为诺干子问题
- 解决这些子问题，当子问题足够小时，可以直接给出答案
- 合并子问题的解成为原问题的解
具体算法有：
归并排序
#伪代码 def merge_sort(A,p,r): if p<r: q = (p+r)/2 merge_sort(A,p,q) merge_sort(A,q+1,r) merge(A,p,q,r) #merge 略
递归式的渐进（主方法）：T(n) = aT(n/b) +f(n)
第二部分 排序
堆排序：数据结构：二叉堆（最大堆，最小堆），可以用来表示优先队列。
快速排序：其最坏性能为O(n**2)，但是平均情况性能为O(nlog(n))。
def quick_sort(A, p, r): if p<r: q = partition(A, p, r) quick_sort(A, p, q-1) quick_sort(A, q+1, r) def partition(A, p, r): '''选择一个数为主元（最后个），将主元置于合适位置，其前面的数比他小，后面的数比他大'''
第三部分 基本数据结构
栈：LIFO，队列：FIFO
链表：指针和数组实现
二叉搜索树：h=log(n)，插入的删除操作；红黑树，根节点是黑色，每个叶节点是黑色，每个红色节点的子节点为黑色，从根节点到叶子节点的黑色节点数相同。旋转。
第四部分
动态规划(dag)：子问题重叠，最优子结构。
第五部分 高级数据结构
第六部分 图算法
图：有向图，无向图。链表、矩阵表示。
BFS:
def BFS(G, s): for u in G.V: u.color = white u.d = inf u.parent = None s.color = gray s.d = 0 s.parent = None q = Queue() q.push(s) while not q.empty(): u = q.pop() for v in G[u].V: if v.color = white: v.color = gray v.d += 1 v.parent = u q.push(v) u.color = black
DFS
def DFS(G,u): time += 1 u.d = time t.color = gray for v in G[u].V: if v.color == white: v.parent = u DFS(G,v) u.color = black time += 1 u.f = time
拓扑排序（DAGS)，强联通分量，最小生成树，最短路径，最大流。