图论算法

1) Breadth-first search

BFS可以看成是从起点开始一个波往各个方向传播，直到通过所有的节点，波的前沿的元素把图的节点分为3类，1.波的前沿已经通过，也就是已经当过波的前沿的节点。2.波的前沿中的节点。3. 其他的元素，也就是还没有被touch过的元素。

波的前沿可以用一个FIFO队列来维护，一个节点出队列的时候，算法会遍历其邻居，根据颜色把白色的也就是波没touch过的元素加到队尾(同时颜色变灰)。然后这元素就彻底出队列了，颜色也变为黑的。(初始队列为空，然后把源加入)

“发现”需要严格定义一下，一个节点$v$被发现指的是这个节点进入队列的时候。$u$记为正在出队列的节点，$v$是$u$的邻居，边$uv$也被记录下来，这个边是发现$v$的边(这个边是breadth-first tree的一个边)。

breadth-first tree会因为邻居节点的不同排序而变化，1) 如果$v_1,v_2$都是$u$的邻居，而且$uv_1, uv_2$都被加入到tree里，$v_1,v_2$的顺序并不影响tree的结构。2) 如果$v$是$u_1$的邻居，也是$u_2$的邻居，$u_1, u_2$的顺序会导致$u_1v$或者$u_2v$被加入到tree里。

最短路的一个性质(Triangle inequality)：如果$u, v$是邻居，那么从任意节点$s$出发的到$u, v$最短路的差是0或者1。

对于不加权的图，路径长度的差别只能是整数，所以上面取值只能是0,1，但是如果是加权的图，如果存在$u$指向$v$的边$(u, v)$，那么到$u$的最短路加上这条边的权给出了到$v$的最短路的一个上界，也就是 $$\delta[v]\leq \delta[u] + w(u, v)$$ 比如如果存在另外一条$u$到$v$的路径长度为0，两个$\delta$是相等的，但是知道边$(u, v)$并不知道这个信息，所以只给出一个上界。

队列的性质：源加入队列的时候队列里只有一个元素，这个元素出栈后，源的邻居(也就是d=1的元素)被加入的队列里，且只有d=1的元素，d=1的元素只会造成d=2的元素被加入到队列里，而且只在队列尾部，因为FIFO，只有当d=1的元素被处理完了之后，才会开始处理d=2的元素。以此类推可以得
a) 队列里的元素d最多差1。
b) 队列的元素d按升序排列。

$d$不小于最短路$\delta$，如果$d[v]=n$，那么根据算法存在一条源$s$到$v$的长度为$n$的路径，$s$到$v$的最短路$\delta [v]$必小于等于$d[v]$。

证明黑色节点的$d=\delta$：显然起点$s$满足$d[s]=\delta[s]=0$，$s$的邻居满足$d=\delta=1$(变黑后)，假设$v$是不满足$d=\delta$的黑节点里面$\delta$最小的，考虑$s$到$v$的最短路，假设$u$是这条最短路上的$v$的前导，那么$d[u]=\delta[u]$，而$d[v] > \delta[v]=\delta[u]+1=d[u]+1$，也就是$u$和$v$的$d$至少差2。根据算法，相邻黑节点的$d$最多差1，矛盾。

算法运行的同时检查图是不是bipartite graph：出队列的节点开始把自己的邻居加入到队列里的时候，如果遇到已经有$d[v]$的元素，可以检查是不是奇偶性相同，如果相同因为$d[v]$就是距离，这说明这两点是bipartite的同一部分，但是他们之间又有了当前这个边，这和图是bipartite的矛盾。

2) Depth-first search

可以用递归或者非递归的方式实现，如果用非递归方式，用一个实际的stack存储要访问的节点队列(对比上面的FIFO队列)，从源开始，把源压入堆栈，检查stack里最上面的元素有没有白色邻居，如果有白色邻居把它压入stack(discover)，以此类推直到发现第一个没有白色邻居的节点(没有邻居也是没有白色邻居)，访问这个节点，并把这个节点染成黑色(finish)，然后从堆栈里把它pop出来，再检查stack里最上面的元素有没有白色邻居。

上面的方法等于是要自己维护调递归时用堆栈里的数据，比如递归方法里的邻居节点循环到什么位置了，递归的时候是调用堆栈维护的，如果不维护可以用搜索第一个白色邻居的方式，如果维护可以在每个节点上加index成员，记录最近检查过的邻居的index，stack pop出来的节点直接去检查这个邻居就可以了。

进栈和出栈和time的关系，进栈之前节点记录发现时间d[v]=time，然后time++，出栈之前time++，节点出栈后记录结束时间f[v]=time。

用递归的方式，考虑从起点开始，第一个孩子的第一个孩子这样递归，可以得到一个linked list，如果图是无回路的就是树，最后会遇到一个没有第一个孩子的叶子节点(记为l)。显然递归函数遇到这个节点的时候会第一次返回，倒数第二层的递归函数里是个循环，循环的访问l的父节点的所有孩子，这个循环会前进一步，访问l父亲的第二个孩子。

如果有回路的图递归函数第一次返回也可能是遇到了以前已经访问过的节点了。无回路的图用递归的方式是不可能遇到已经被touch过的节点的，所以tree遍历的时候不记录节点是不是被访问过(还因为tree是有向图，父节点指向子节点)。

3) 拓扑排序

有向图的拓扑排序的序的定义$u > v$如果存在$u$指向$v$的边。

Depth-first search在有向图里发现back edge说明图里有cycle，而且cycle必然会造成depth-first search里发现back edge。

算法：排序队列起始为空，开始depth-first search，当一个节点finish的时候，把这个节点放到排序队列的前端，depth-first search结束的时候的排序队列是图的一个拓扑排序。

如果存在$u$到$v$的edge $u\rightarrow v$，那么$f[v] < f[u]$

4) 有向图的强连通分支

定义：同一个强连通分支里的任意两个节点之间有路径连通，特别的u到v有路径且v到u也有路径。

定理：有向图的转置是把所有的边反向，一个有向图和它转置的强连通分支相同。

定理：如果把强连通分支合并成一个节点，得到的有向图是无回路有向图(dag)。如果在图上做一个depth-first search，取强连通分支$C$里面$d$最小的为这个$C$的$d$(也就是里面最早被发现的节点)，取$C$里面最大的$f$为这个$C$的$f$(最后结束的)。

定理：如果存在强连通分支$C$到$C'$的边$(u, v)$，那么$f[C] > f[C']$。(边$(u, v)$的存在实际上断绝了$C'$到$C$存在边的可能)。考虑图的转置，只要把结论反过来就可以，因为$f$和$C$和转置没有关系，转置不会改变$f$或者$C$。

算法：先在有向图$G$上运行depth-first search，记录每个节点的finish时间$f[u]$，在图的转置$G^T$上运行depth-first search，但是主循环里面的顺序按$f[u]$的降序。第二个depth-first search输出的depth-first search forest里每个tree都是一个强连通分支。
第二个depth-first search起始的时候在$f$最大的强连通分支上运行，也就是原图$G$上只有这个强连通分支只有出去的边，转置后$G^T$上同一个强连通分支只有进来的边，所以这个强连通分支的节点访问结束后会返回主循环，而不会碰到其他强连通分支，当进行到第$k$个强连通分支的时候，$k-1$已经是黑色的，而第$k$个连通分支只有从没访问过的强连通分支进来的边，出去的边都是指向已经访问过的前$k-1$个分支。

5) 最小支撑树

支撑树可以看成边的集合，包括这些边的端点。

Kruskal's algorithm(贪心算法)：$E$ 为所有边的集合，$A$初始为空集，每次从$E$中选出权重最小的，并且加入$A$后不在$A$里产生回路的边加入$A$中，得支撑树之后算法结束。

实现：找剩下的边权重最小的很简单，只要把边按权重排序，每次取最小的即可。找到一个权重最小的后验证是不是会造成回路要用disjoint sets，起始的时候用make-set操作把图里的所有节点都做成子集，用方法find-set检查两个节点是不是已经在同一子集中了(如果已经在同一子集中，加入这个边会产生回路)，如果在就抛弃这条边，如果不在，把边放到A中，并且把两个找到的子集合并。所有的边都检查过后算法结束。

注意任何时候，保留的边和所有的节点构成的集合是一个图，里面没有回路。算法结束的时候结果是一个连通的图，而且没有回路。

定义Cut：无向图$G$的一个cut是其节点集合的一个划分，分成两部分。如果一条边的两个端点分属两个子集，则称这条边cross这个cut。A是边的集合，说一个cut respects集合A，意思是A里的所有边都不cross cut。

safe edge：边的集合A是一个最小支撑树的子集，如果加入边$uv$后还是一个最小支撑树的子集，称$uv$为A的safe edge。

定理：连通无向图$G$，边的集合A被一个最小支撑树包含，一个cut respects集合A，那么corss这个cut的所有边里面权重最小的边是A的safe edge。

Prim's algorithm：也是贪心算法，不过在往A里面加入新的边的时候要求边的一端连接A，另一端不连。

实现：当算法选择一个新的要加入到A里的边和节点的时候，所有和A相连的边必须都考虑过。

每个节点赋予一个key，初始的时候所有节点的key都是$\infty$。所有和A相邻节点的key都会变成连接它和A的权值最小的边的weight。

a) 把图里所有节点放到一个按其key维护的优先队列里，任取一个节点作为支撑树的起点，把它的key置0，父亲指针置空。

b) 每次从优先队列里把key最小的u抓出来，检查所有u的邻居，如果邻居在队列里(记为v)，并且连接邻居的边(u, v)的weight比v的key值小，更新v的key为这个weight(就是v出发的cross cut的最小的边)，并将v的父亲指针$\pi[v]$指向u。

c) 在从优先队列里抓最小值之前，所有的不在队列里的节点的邻居都被考虑过，也就是cut的cross edge都反映到他们邻居的key里面了。

6) 最短路算法

最短路不能有cycle，所以最长的最短路的边数小于等于$|V| - 1$。算法结束后对每个节点除了起点，都定义了一个前导$\pi(v)$，前导是和有向的边相反的，最短路包括$(u, v)$那么$\pi(v)=u$。

Bellman-Ford algorithm：复杂度$O(VE)$，允许有负权值的边，但是不允许有从源reachable的负权值cycle，算法会侦测出这样的cycle。
RELAX函数是对一个边的操作，传入边的两个端点的$d$值，和边$(u, v)$的权值，检查$d[u], d[v], w(u, v)$是不是满足最短路的性质，并进行修正$d$和$\pi$。图中的最短路的长度最长为$|V|-1$条边，Bellman-Ford algorithm做$|V|-1$次对所有边的RELAX，第一次边数为1的最短路终点节点的$d$变为最短路的长度，第二次边数为2的最短路的终点节点的$d$变为最短路的长度，所以$|V|-1$次循环后所有的最短路终点节点的$d$都变成最短路的长度。

利用Topologically Sort的结果：Topologically Sort结束后，得到了一个节点的序，所有的边都是前面的节点指向后面的节点，一个按这个序的节点的循环一次，对每个节点RELAX其adj list里的每个边，这些边都是这个节点出发的，循环结束，算法结束。
分析：每个从源头reachable的path都是按这个path的边的顺序RELAX的(可能不是一条path结束另一个开始，是同时进行的)，所以所有节点都处理过后，$d$，$\pi$构成了最短路tree。

任务顺序：用DAG建模，有向的边是任务，wight是任务需要的时间，如果两个任务有直接依赖，把两个边直接接起来，那么图里最长的路径是完成所有任务需要的时间的下界。用最短路算法可以解决这个问题，只有把权值全部变为负的，然后运行算法。

Dijkstra's algorithm：这个算法和Prim's algorithm最小支撑树的算法很类似，在Prim's algorithm算法里用一个优先队列维护cut另一边的节点，队列最上面的是cross cut的最小的边，所以key是某一条边的weight。在这里key是节点的$d$值，从优先队列里抓出来的最小值的节点去向是S，S初始的时候只有源头一个节点，每次从优先队列里抓出来key最小的节点(记为u)，遍历u的所有邻居，update他们的$d$值，和Prim's algorithm里面的分析一样，所有S里的节点的邻居都是考虑过的。
分析：只需要证明当节点$u$被加入S的时候$d[u]=\delta(u)$，假设$u$是第一个这样的元素不满足这个条件，也就是$d[u] > \delta(u)$，设$p$为实现$\delta(u)$的最短路，如果$u$在这条路径上的前导在S里，那么前导指向$u$的边RELAX的时候会更新$d[u]$为$\delta[u]$；现在假设这个前导不在S里，记为$y$为最后一个不在S里的路径上的前导，有$d[y]=\delta[y]$，根据算法，因为当$u$被抓出来的时候$y$也在优先队列里，所以这时候$d[u] \leq d[y]$，因为$p$是最短路，有$d[y]=\delta[y]\leq \delta[u]\leq d[u]$，所以$d[u]=\delta(u)$。

7) All-Pairs Shortest Paths

用GDPP来建模最短路

a) 定义$\Omega_k$为所有边的个数最多为$k$无环路径，显然$0\leq k \leq |V|-1$。

b) $\Omega_{k-1}$里的entries变换为$\Omega_{k}$里的entries的方式是，任取一个节点$v$作为终点，考察到达这个节点的边，比如$(u, v)$把所有长度最多为$k-1$终点为$u$的无环路径加上$(u, v)$，并且加上后不能有环，就得到了$\Omega_{k}$里的entries。

c) 因为我们要找的是最短路径，所以$M$是变换的代价，定义为$M(p^{(k-1)}, p^{(k)})=w$，其中$w$是新加上边的weight。

d) 为了定义最优值函数$\mathcal{F}$需要把$\Omega_k$分类，因为最优值函数不是在整个$\Omega_k$上取值，定义$\Omega_{k,ij}$是$\Omega_k$的子集，约束是路径的起点为$i$，终点为$j$。$\mathcal{F}(\Omega_{k,ij})$定义为里面的路径长度最小的路径。

e) 递归关系定义为： $$\mathcal{F}(\Omega_{k,ij}) = \min_{l}[ \mathcal{F}(\Omega_{k-1,il}) + w(l, j)]$$ f) 用矩阵维护$\mathcal{F}(\Omega_{k,ij})$的值，起始的时候这个矩阵是weight矩阵，$i=j$为0，$i$到$j$无边为$\infty$，得递归下一步矩阵$\mathcal{F}(\Omega_{k+1,ij})$的时候，先初始化为正无穷，因为要记录$\min$的值，遍历矩阵的$i,j$，当$i,j$定了以后，遍历递归关系里的$l$每次和$\mathcal{F}(\Omega_{k+1,ij})$对应的元素比较，如果较小就更新其值。

8) Maximum Flow

Markov Chain

1) 单步过度概率矩阵$P=(p_{ij})$，其中$p_{ij}$是状态$i$到状态$j$的概率。也就是条件概率 $$P(X_n=j|X_{n-1}=i)$$ 2)state的选择，初始不是Markov过程的过程可以转变成Markov，比如明天下雨的概率依赖于今天和昨天的情况。这时候可以定义状态为连续两天天气状态的所有可能。

3) 直线上的random walk，状态空间为直线上的整数点，假设$X_n=i$，$X_{n+1}$只能是$i-1,i+1$，也就是 $$ \begin{array}{l} &P(X_{n+1}=i+1|X_n=i)=p\\ &P(X_{n+1}=i-1|X_n=i)=1-p \end{array} $$ 4) 如果一个Markov Chain进入某个状态后不会变成其他状态，这些状态称为absorbing states，用转换概率表达式 $$ \begin{array}{r} &P(X_{n+1}=as | X_n=as)=1\\ &P(X_{n+1}=\text{other states} | X_n=as)=0 \end{array} $$ 5) n-step transition概率定义为$P^n_{ij}=P(X_{n+k}=j | X_k=i)$，Chapman-Kolmogorov方程 $$P_{ij}^{n+m}=\sum_{k=0}^\infty P^n_{ik}P^m_{kj}$$ 是简单的不同path的概率的和式。式中的概率都是条件概率。并且上面的式子正好是矩阵相乘。根据归纳法可知$P^n_{ij}$是一阶转移矩阵n次方$(P_{ij})^n$的元素。

5) n-step transition中n可以为0，这时候transition矩阵是单位矩阵。两个状态称为accessible，如果存在n满足$P^n_{ij} > 0$。互相accessible的状态是称为communicate，记为$i\leftrightarrow j$。communicate是等价关系。如果一个Markov Chain的所有状态互相communicate，那么这个chain称为irreducible。

6) 考虑时间趋于无穷的时候情况，状态有这样的分类。$f_i$记为当时间趋于无穷的时候状态$i$至少会被到达一次的概率。如果$f_i=1$状态称为recurrent，如果$f_i < 1$称为transient。

7) 如果一个Markov Chain在某个时间进入了某个状态$i$，Chain等价于从$i$起始，并且如果$i$是recurrent，那么Chain将会infinitely often进入$i$。所以recurrent和transient可用chian进入这个状态次数的期望来刻画。

8) 假设chain的起始状态是i，$I_n$为indicator，第$n$步的时候如果chain在状态i则$I_n=1$否则$I_n=0$，chian进入状态i次数的期望为 $$E(\sum_{n=0}^\infty I_n | X_0=i)=\sum_{n=1}^\infty P^n_{ii} $$ 同样的道理，transient的数学意义，当时间趋于无穷的时候状态只会被访问有限次。显然transient和recurrent是互斥的。

9) communicate把chain的状态分成等价类，每个等价类状态要么全是recurrent要么全是transient。因为recurrent意味着一旦有可能进入这个状态，那么将会无限次的进入这个状态，加上communicate，和他在同一个等价类的状态都是这样的。

10) 再考虑上面的random walk，所有的状态都是communicate的，所以要么全是recurrent，要么全是transient，可以证明，一维的时候如果$p=\frac{1}{2}$那么所有的状态都是recurrent的，否则都是transient的。二维的时候有类似的结论，但是当维度大于2的时候所有的random walk状态不论$p$是多少都是transient的。

11) n-step transition概率矩阵记为$P^{(n)}$当$n$趋于无穷的时候得到的极限情况。对于ergodic Markov Chain 极限$\lim_{n\to \infty}P^n_{ij}$存在，并且极限值不依赖于$i$，也就是说无论起始状态是什么，n趋于无穷的时候最后达到的状态$j$的概率是固定的，所以可以记为$\pi_j$，(可以构造一个代数方程，$\pi_j$可以用解代数方程的方法求出，不用求极限)。

数据结构

1) 一般知识

几何级数求和 $$S_n=\sum_{k=0}^n ax^k=\frac{a-ax^{n+1}}{1-x}$$ 记忆方法，(第一项)减去(最后一项的后面的一项)除以(1减去等比)。

二进制
二进制数乘2是移位，对二进制小数也一样。给一个小数，要得第一位二进制数字，把数乘以2(等于是把第一位二进制数字移到小数点左边)，然后把整个数和1比较大于1说明第一位二进制数字是1，小于1说明第一位二进制数字是0。

几何解释，二进制小数相当于把区间(0,1)无限二分，如果第一位是1，说明在大于1/2的部分，如果是0说明在小于1/2的部分，以此类推。如果把二进制小数看成二分查找，一个小数可以写成$$\frac{a_1}{2^1}+\frac{a_2}{2^2}+\frac{a_3}{2^3}+\cdots+\frac{a_n}{2^n}$$ 其中2的幂次可以看成一个Binary Tree的第k层edge的一个选择，乘以2等于是把选择都往上提一层。

如果$2^{m-1}\leq n < 2^m$，那么用二进制表达$n$要$m$ bit，比如32位的二进制数可以看成$[0, 2^{32})$区间里的二分查找，不过是从最高位，最左边的(二进制小数也是最左边)开始，如果是1，说明这个数大于$100000000....=2^{31}$，以此类推。

这个BST的记忆方法，注意二进制里面的0,1对应的是树的edge，而不是节点，但是其实每个edge和它的目标节点是一一对应的，0,1完全可以标注在edge上，把root看成没有意义的节点，以为没有edge通向它。树的第一层的edge对应二进制数的最高位，这个BST的第k层edge都对应了前k位的二进制表达，比如第二层是前两位，也就是00xxxxxx, 01xxxxxx, 10xxxxxx, 11xxxxxx，其余的数字是未知。决定第3位的时候是和ab100000比较，如果比其大走的边为1，到达ab1xxxxx，如果比其小走的边为0，到达ab0xxxxx。总位数对应了树的高度，树每增加一层，第一层代表的数的含义要增加一个二进制位。

BST的第k层的最左边元素的子树的含义是：用不到前k位。任取一个这样的节点，下一步是和0000001000000...(1前面有k个0)比较，小于那么继续沿着最左边的edge走，大于，靠！终于离开最左边了。

对于任意一个整数n，要用二进制表达，考虑一个无限的BST，往上看不到root，但是任意给一个节点，我们知道这一层是根据判断倒数第m位决定往下走的，这时候其实是知道往下还有m-1层，因为是倒数吗。也就是我们要知道n的倒数第几位不是0，也就是什么时候离开BST树的最左边的edge的，也就是什么时候开始大于某个000000100000000$=2^m$了，(m的含义，注意m和十进制里的科学计数法类似，一万是$1\times 10^4$，这里4其实是0的个数，同样的1000$=1\times 2^3$，这里m也是0的个数，显然1在第倒数m+1位上)。可以看出$2^m$需要m个0和一个占位用的1来表达，也就是$m+1$ bits。

现在离开最左边的edge了，继续往下，这时候可以忽略第m+1位了，因为后面的子树里的元素第m+1位都是1，算术上，忽略就是从n里减去$2^m$。

用余数法得二进制表达可以这么理解，任意一个整数n我们知道它是那个无限BST里的一条轨迹，而且从最底层往上，这条轨迹总会接到BST的最左边的边，否则这个数就是无穷大了，把这个数除以2的对轨迹的影响是轨迹形状不变，沿着BST最左边的边往下平移一层，然后把超过最底下一层那个数字是0或1记下来然后扔掉。

gcd and lcm
$$\gcd(m,n)=\max\{k\ |\ k\setminus m \text{ and } k\setminus n \}$$ $$\text{lcm}(m,n)=\max\{k\ |\ m\setminus k \text{ and } n\setminus k \}$$

2) Heap

Heap是基于tree的数据结构，对于max-heap，heap要求父节点大于子节点。heap对tree的子节点个数没有要求，不同的个数都可以实现heap。Binary heap要求任何一个节点最多有两个子节点。Binary heap可以用array来存储，相当于一个三角形，第一层是root，第二层是root的两个子节点，第三层是接下来的4个子节点，以此类推。把这个三角形放平就得到按array存储的binary heap。

用arrar存储heap的时候元素的定位：

a) 对于不同base的array(0或者1)，先数个数，如果是base 0的就减去1得index。

b) 如果一个$m$层的heap是满的，那么元素个数为$2^0 + 2^1 + \cdots + 2^{m-1}=\frac{1-2^m}{1-2}=2^m-1$，可以把$m$层的heap分为：前$m-1$层$2^{m-1}-1$个元素，第$m$层$2^{m-1}$个元素。

c) binary heap的第$2^{m-1}$个元素是三角形的第$m$层的第一个元素。

d) 考察第$2^m+l$个元素，$l$的含义是在$m+1$层这个元素前面有$l$个元素(比如$2^m+0$是$m+1$层的第1个元素，在这层前面有0个元素)，它的子节点在$m+2$层，记为第$2^{m+1}+x$个，检查第$m+2$层的情况，如果$2^{m+1}+x$是left child，那么它前面的在这层有$2l$个元素，他们是$m+1$层元素$2^m+l$之前的元素的全部子节点，所以$x=2l$，也就是$2^{m+1}+x=2(2^m+l)$。
结论就是第$2^m+l$个元素的left child是第$2(2^m+l)$个，如果这个元素的index是i(base 0)，那么他是第i+1个，所以left child是第2(i+1)个，所以left child的index是2(i+1)-1=2i+1。

e) 判断一个节点$k$是不是有孩子只要看$2k$是不是超出heap的范围了。反过来对于大小为$n$的heap，那么第$n/2$就是最后一个有子节点的节点(如果array是base 0的，第$n/2$个的index就是第$n/2-1$)

堆排序：分为两步，1.把输入的队列变成heap。2.把root弄出去(如果是in-place，那就是减少队列里是heap的部分)，然后把最后一个元素放在root的位置上，然后shift-down，这样递归直到heap空。

往里heap里加元素：放heap的最后，然后shift-up。
去掉heap的root：把root和heap的最后一个元素交换，去掉最后一个，然后把新root shift-down。因为把root去掉后需要从别的地方移一个元素过来填充这个位置，移最后一个破坏最小。

修复被破坏的heap：上面提到被破坏的情况，可以看出，新元素总是破坏heap的根源，唯一安全的去掉heap里元素的办法是去掉最后一个。如果root是新的，那么它需要被shift-down，如果最后一个元素是新的，那么它需要被shift-up。
对于任何一个array，可以看成是被破坏的heap，恢复的方法是找到最后一个有子节点的节点，开始shift-down(因为从这个节点开始往后的部分array没有破坏heap属性的元素)，然后这个节点的前一个(一定是有子节点的)，shift-down，一直到root。这种方法比从空heap开始建立新的要快(O(n)和O(nlogn)的差别)。

b-heap:把子树限制在一个虚拟内存的page上以提供查询速度， http://queue.acm.org/detail.cfm?id=1814327

任何tree都可以用"Left child-Right sibling"的编码方法存储为一个binary tree，

3) Binary search tree

条件：当前节点比left大，比right小，任何子树都是Binary search tree。在其中搜素一个元素其过程类似折半查找，但是坏的情况是tree不是balanced，就像折半查找不是从中间折的，是从最远的那头折的。最坏的情况显然是要遍历整个tree。

从sorted队列得到Binary search tree，可以想象一个排好序的队列，开始随机的选择一个元素，把队列从这里折一下(去掉选中的元素)，得到两部分队列分别作为left和right子树的元素，分别再随机的折断，递归下去直到没有元素剩下。

插入一个新的节点就是从root开始和当前节点比较，小的放left子树里，大的放right子树里，以此开始递归。

中序前导和后续(右边是向后)：in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree。当需要删除tree里一个有两个child的节点的时候需要把这个节点和它的中序前导和后续交换，然后再把那个节点删除，然后把其子树(最多会有一个子树)接到删除的节点。原因1.中序前导最多只有一个child，2.他们是在序上的本节点最近的节点，上面的操作不会破坏序。

从递归上考察中序后续：首先后续是在right子树上，因为中序是访问完本节点后才访问right子树，递归的访问right子树的时候，第一个被实际访问的是递归的时候遇到的第一个没有left child的节点，也就是最left的节点，最left才能保证递归进入right子树后，一直在进入下一个堆栈，没有出栈的动作，也就是没有任何一个节点被访问过。

大小关系，最left的元素是最小，因为任何一个其他元素都可找到一个祖先，最left和它分属这个祖先的left子树和right子树。

4) Tree rotation

Fact：left子树里的任何一个child都可以做left child。
Fact：里面B的父节点发生了变化，但是B的level并没有变。
Fact：A的level减少了1，换句话说，做right rotation的时候，left子树的left子树level减少了1。

Tree rotation的时候子树的的取值范围

对任何的BST，两个子树的取值范围是对当前节点代表的子树的取值范围的一个划分，当前节点的key是用来划分的新边界。

4) AVL tree

根据上面Binary search tree的构造方式，BST有时候会很不平衡，而很多tree的操作都是和tree的高度成正比，AVL tree是一种Binary search tree，多的约束是每个节点的balance factor只能是-1,0，1超过这个范围要用Tree rotation的方法变化到满足balance条件，这样可以使得tree更加balance。

AVL tree要求比red-black tree严格，但是查找(就是一般的BST查找)更快，因为严格，插入和删除比red-black tree慢。

高度的递归定义当前节点的高度是它的两个子树的的高度里面较大的加1，空树的高度为0。

按BST的算法插入新的节点后要检查本节点以及其祖先节点的balance factor是不是满足balance条件，如果不满足可能的情况有下面四种。

不满足就是有个节点的balance factor边2或者-2了，两种情况是对称的，不管哪种tree都要以这个节点为支点向层少的那一边做Tree rotation，但是变换之前要保证层多的那一边的子节点的不平衡的方向和本节点的不平衡的方向一致，否则对那个子节点做Tree rotation(如果不先这样，可能一下子由2变-2，没恢复balance)。

删除节点和和BST一样，但是删除完了以后要从被删除的节点的位置开始往上直到root检查balance factor，消除不balance的情况。
reference: Lecture Notes on AVL tree

5) B-Tree

B-Tree里节点和key的概念是分开的，每个节点有多个key，这样其子节点对应回来和key相对应，在节点内部key是排好序的。在BST里搜索的时候是比较节点(其实是节点和key重合了)，B-Tree里是比较key，我们知道BST里把父节点从大小上正好把两个子树隔开，B-Tree类似的如果父节点有N个key，这N个key把N+1个子树从大小上隔开。

|key|key|key|key|key|key|key|key|key|

其实子树不是和key对应的，是和key之间的缝隙对应的(最边上的"|"可以看成特殊的缝隙)。

根据上面的结构，在B-Tree里搜索的时候首先是在本节点的key里用折半查找搜索，如果找到搜索结束，如果找不到会得到两个key，一个大于当前找的值，一个小于当前找的值。按上面说的key和子树直接的关系，我们知道要找的值在这两个key夹的那个子树里面。

插入新的key：插入之前先要搜索，如果搜到发现要插入的key已经在里面了，更新key指向的数据，如果到B-Tree的叶子节点还没找到，那么就把这个key插入到这个节点里的正确位置上。但是B-Tree对节点里key的个数是有约束的，不能大于某个常数，比如不能大于B。现在假设新key插入后，这个叶子节点的key的数量为B+1个，这时候可以用B-Tree的分裂操作，把节点里的key分为三份，各B/2,1,B/2个key。

我们知道这个叶子节点对应了其父节点的一个缝隙，三份里面中间的那个key插入到父节点的这个缝隙里，这样得两个新缝隙，分别指向B/2和B/2这两个新节点就可以了。如果父节点也满了，继续往上的递归就可以了。

删除key：删除一个非叶子节点里的key，我们知道这个key隔开了两个子树，如果两个子节点里的key的个数都是B-Tree要求的最小值，那么可以把他们合并变成一个节点，删除他们父节点的key后两个缝隙合并成一个，合并的节点正好指向这个新缝隙。如果这样的合并不可能，需要把这个key的直接后续(或者直接前导)拿过来代替，他们都是可以作为两个子节点的分隔，这个直接后续必然在子树里，一直递归到叶子。如果叶子里的key被删除或者被当后续拿走，这个叶子节点可能会违反B-Tree节点里的key不能少于B/2个，这时候有两种可能：

1.邻居有多余的key(大于B/2个)，可以借一个过来，但是不能直接移，因为两个子树大小上被父节点的key隔开了，直接移必然会破坏大小顺序，用的方法是把多余的key移到父节点，然后把隔开他们的那个key移到本节点，这样不影响大小关系。

2. 左右都没有多余的key，这时候可以选择一个邻居和它合并(合并后为B/2+B/2-1个key)，和刚才同样的道理，不能直接合并，大小上被父节点的key隔开了，用的方法是直接把这个key从父节点拿下来一起合并，得的新节点是B个key不违规。但是父节点可能违规，递归的往上就可以了。

Red-black trees are 2-3-4 trees disguised as binary trees.
reference:
http://perl.plover.com/BTree/article.html
http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html

7) Red–black tree

2-3-4tree是节点的子节点数允许的个数是2,3,4的B-Tree，当插入新key的时候有两种方法用于保持2-3-4规则(2,3,4子节点<==>1,2,3key)。1. 上面B-Tree里插入新key的办法，违反的时候分裂，移动一个key到父节点。2. 插入新key的时候要先从root开始往下搜索，在这个路径上检查每个经过的节点，如果发现是4节点把它分裂，插入的办法和以前一样。

在2-3-4tree，2节点已经是最简单的了，只有一个key，和一般的BST里面的节点是一样的，3,4节点可以按如下的方式转换成单个key的节点的组合：

3节点有两种变化，如果限制只能选往左倾斜的哪种得到的tree称为Left-leaning red-black trees，这个tree对黑色的边是完全平衡的，也就是算每个叶子节点的高度的时候忽略红色的边。

3节点的两种变化差的是一个tree rotation，用B-Tree的角度看tree rotation，两个key是节点里的key，两种情况是一样的，其中一个要被选出来作为局部root，约束是作为局部root的key只能带一个他们共同的子节点，另一个非局部root的key带剩下的两个子节点，所以一旦root选定结构就定了。root选右边的，结构往左倾斜，正好相反。

算法(换孩子，然后换root)：left tree rotation，也就是现在内部的left key是局部root，root的性质是一个BST子节点被另一个内部key占有了：

a) 内部key： K1, K2 (K1==root <==> K1.right=K2)
b) 三个B-Tree子节点：K1.left, K2.left, K2.right.

先保证K1和K2有变量hold住，然后把三个子节点中间的那个抓出来K2.left，赋给老root K1.right=K2.left(K1.right==K2已经有变量K2 hold了)，然后理顺内部key的关系，K2.left=K1。
所以体现rotation的一步是换root：K1.right=K2 ==> K2.left=K1，前一步是换孩子。

存储：根据上面的描述，2-3-4tree可以存储成BST，但是需要能识别哪些key实际上是一个B-tree节点内部的key，方法是把这些key之间的边标记成红的，因为BST里面节点和入边是一一对应的(除了root)，所以可以把这个边的信息存储到节点里，如果入边是红的，节点记为红的。上面的rotation里面的红边永远是进入非root的那个节点，所以rotation之后把非root的那个K1变红。

插入：插入新节点的时候，先按BST的方式插入新节点，插入后把这个节点标记为红的，也就是和父节点的连接边是红的。然后开始检查，

a) 如果父节点不是红的，那么对应的是我们新产生了一个2-3-4tree里的3节点。

b) 如果父节点也是红的，对应的是往2-3-4tree里的3节点里加入一个key产生一个新的4节点。

c) 4节点标准形式的一个变换是反转颜色，这种4节点有3个key，中间的那个是root，另外两个是BST里的root的子节点，红的，反转颜色就是把两个子节点边黑，然后把root变红。对应的是B-Tree里的节点分裂，并且把中间的key合并到上面的节点。

插入的时候，递归往下每次遇到左右孩子都是红节点的时候就进行反转颜色操作(递归入下一个堆栈之前)，这样能保证插入的时候只有a),b)两种情况，而不会直接往一个4节点里插入。

d) 修正非标准的3,4节点可以在递归返回的时候去做，调用rotation函数，因为rotation函数每次返回的都是新的局部root，所以不会影响递归往上的过程。先修复单个的右倾斜，然后修复连着的两个左倾斜。

e) 如果把反转颜色放到递归返回后rotation修正之后做，LLRB就变成了2-3tree，永远不可能有4节点出现。

f) 可以看出操作反转颜色和rotation都不改变所有节点的黑色边的level，不会破坏黑色边的balance。

删除最大：删除最大的想法是先把最大的那个节点变成红的，这样删除的时候就不会破坏黑色边的balance，方法是从root开始把一条红边一直搬运到max节点。

a) 因为讨论的LLRB，所以树的最右边的路径的边都是黑的，不可能有红的。

b) 递归函数deleteMax(current_node.right)被在递归里被调用的时候就是往下移了一层，递归的要求是要么current_node.right是红的，要么current_node.right.left子节点是红的，要么current_node.right.right子节点是红的。这三个条件使得最后得到max的时候max是红的。

c) 首先是检查current_node.left是不是红的，如果是红的，right rotate，完事之后往下移动的条件就满足了，可以调用deleteMax(current_node.right)递归。

d) 如果current_node.left不红， right rotate也没用，检查current_node.right如果也不红，而且current_node.right.left也不红，这时候以current_node为基点颜色反转，颜色反转后考察以current_node为root往下两层的子树，第二层有4个节点，因为是LLRB所以两个right不可能是红的，我们又知道current_node.right.left也不红，只有current_node.left.left可能是红的。

e) 如果颜色反转current_node.left.left不红，什么也不用做，current_node.right边红了，可以开始递归，如果current_node.left.left是红的，那么要做以current_node为基点的right rotation，然后在以current_node为基点的颜色反转，得到的结果是current_node.right.right变红了，这时候就可以递归往下了。

删除最小：删除最小和删除最大差不多，只是有时候颜色翻转后，如果需要rotation会多一次。并且我们不需要用rotate left了，因为是LLRB，所以当前节点的子节点如果本来有红的一定是left是红的。如果没红的，要颜色翻转。递归的要求变为current_node.left，或者current_node.left.left是红的。注意子节点里的right红只会是颜色翻转带来的，只会影响到当前节点的直接孩子，current_node.left.right不可能是红的。

删除后，需要在每次递归出栈的时候，修复违规的情况，包括right倾斜，连着的left倾斜，和左右节点都是红的情况。

删除任意元素：可以约化为删除最小最小，del_node = min(del_node.right)，deleteMin(del_node.right)。但是上面颜色的变换要从root搜索的时候就开始，这样才能保证deleteMin(del_node.right)的行为和deleteMin(root)一致。

reference，解释2-3-4tree和Red–black tree之间的关系，http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

8) Binomial heap

Binomial heap是一堆Binomial tree的集合，Binomial tree是递归定义的，第k阶的Binomial tree是两个k-1阶的Binomial tree接在一起，直接把一个当成另一个的root的孩子。Binomial tree节点的个数只能是$2^n$。k阶Binomial tree的root的degree是k，所以可以从root的degree得到这个tree里的元素的个数。

Binomial heap要求
1. 集合里的Binomial tree满足minimum-heap property也就是孩子比父亲大。
2. 不能有相同节点数的Binomial tree。

Binomial heap里的Binomial tree的root节点被存储在一个linked list里，按各个树的阶排列，这样merge的时候只检查相邻的tree就可以了。

merge两个Binomial heap，先把两个heap的root linked list合并，然后merge同阶的tree直到满足heap的要求。

删除最小的节点，从root linked list里找到最小的节点，然后删除，其子树分裂成多个Binomial tree，把这些Binomial tree集中起来生成一个新的Binomial heap和原heap合并。

删除任何一个节点，把这个节点的值变成-inf，然后shift-up，到root后，运用操作删除最小的节点。

插入一个节点，把这个节点看成一个单独的Binomial tree，加入到heap里，然后开始merge。

数量：n阶的Binomial tree有$2^n$个元素，根据Binomial tree的构造过程，Binomial tree每增加一阶高度上看，增加了1，高度=被插入的tree的高度加上root，所以高度是n。

第d层的节点数量：如果把第0层的节点都标上为$x^0$，第1层都标上$x^1$，第$d$层标上$x^d$，横向求和得到$x^0+a_1x^1+\cdots +a_dx^d+\cdots + a_nx^n$。当tree的阶增加1的时候相当于于乘以x，也就是被插入的那个n阶Binomial tree从$x^1$开始算。相当于$x^0+a_1x^1+\cdots +a_dx^d+\cdots + a_nx^n$加上$x^1+a_1x^2+\cdots +a_dx^{d+1}+\cdots + a_nx^{n+1}$也就是$(1+x)^n(1+x)$。
由以上很容易通过归纳法的到d层节点个数是${n\choose d}$。

9) Disjoint Sets

Disjoint Sets是把一个元素的集合表达成不相交的子集，方式是每个子集选一个代表元，数据结构有一个方法是Find-Set，这个方法输入任意一个元素，返回这个元素所在子集的代表元。判断两个元素是不是在同一子集的方法是对他们调用Find-Set，然后比较代表元是不是一样，如果一样则两个元素在同一集合里。

子集里的每个元素都维护一个指向其代表元的指针，这使得Find-Set的时间复杂度是$O(1)$。子集可以用链表存储，UNION操作用于合并两个子集，最费时间的地方是update其中一个子集的元素的代表元指针指向新的代表元。

MAKE-SET操作是简单的创建一个新子集，只包含传入的新元素，这个元素自然是新子集的代表元。

当用链表实现Disjoint Sets的时候，可以维护一个子集的size，每次UNION的时候把小的子集接到大的子集里，这样update指向代表元指针的时候会更快一些。

用forests实现Disjoint Sets，每个子集是一个树，每个节点都指向一个父节点，最终指向代表这个树的root。root指向的父节点指向自己。UNION操作就是把一个树的root指向另一个树。

树有可能很不平衡，有两个办法可以改变这种状况，1) union by rank是每个tree的维护一个rank，rank和tree的高度相关，每次union的时候把rank小的tree的root指向rank大的tree，这样可以使得到的新tree更平衡。2) path compression在用forests实现的Disjoint Sets，Find-Set是个递归的过程，从传入元素到root是一个路径上递归，在递归出栈的时候把路径上的元素的指针直接指向root，这样就把tree变的更平了，可以提高以后操作的运行速度。

应用：1) 维护无向图的联通分支。2) 判断加入一个新边到图里是不是有回路，假设a,b直接没有边，要加一个，如果a,b根据find-set已经在一个联通分支里，那么加入新边会产生回路。

Fibonacci heap

Entropy

对一个离散的概率空间$(\Omega=\{x_1, x_2, \cdots, x_r\}, P)$，概率测度的$P$的墒定义为 $$H=-\sum_{j=1}^rp_j\ln p_j$$ 设$\omega=(\omega_1, \omega_2, \cdots, \omega_n)\in \Omega_n$，那么 $$ \begin{align} P(\omega)&=P(\omega_1)\cdots P(\omega_n)\\ &=p_1^{\nu_1^n(\omega)}\cdots p_r^{\nu_r^n(\omega)}\\ &=\exp(\sum_{j=1}^r\nu_j^n(\omega)\ln p_j)\\ &=\exp(n\sum_{j=1}^r\frac{\nu_j^n(\omega)}{n}\ln p_j)\\ &=\exp(n\sum_{j=1}^rp_j\ln p_j)\exp(n\sum_{j=1}^r(\frac{\nu_j^n(\omega)}{n}-p_j)\ln p_j) \end{align} $$ 信息熵是随机变量的分布的泛函定义为 $$H=-\sum_{j=1}^rp_j\log_2 p_j$$ It is the number of bits on average required to describe the random variable.比如均匀分布的离散随机变量，取值空间为32个值，每个值的概率为1/32，直观的可以看出需要5bit来描述这个随机变量的取值，这和信息熵公式计算的结果是一致的。

对于一段随机字符，全部的知识是知道每个字符什么时候出现，最少的信息是什么都不知道，知道每个字符出现的概率是部分知识。 熵的含义，如果一个信息源输出字符序列，已知的信息是字符表里每个字符出现的概率，那么检查到一个出现概率很高的字符的时候得到的信息要少。比如a, b构成的10个字符的序列，字符a出现的概率为9/10的，如果第一个出现的字符就是b，那么我们知道后面9个都是a，字符序列完全确定了，可见b出现带来的信息量很大。反过来如果第一个出现的是a，后面9个还是不能确定。

条件期望

0) 条件期望计算的一个前提条件是，用于条件的概率是可以计算的。

条件期望$$E(X|Y)$$是r.v. $Y$的函数，所以也是个随机变量。这个r.v.的一个性质的是它的期望和$X$的期望相等。

我们知道r.v.$X$带了了底部概率空间的一个划分，划分的每个子集里，$X$的取值是一样的。加入另一个r.v. $Y$带来了底部概率空间的另一个划分，对这个划分我们定义了条件期望，也就是在$Y$带了的划分上对$X$求期望。

$Y$只是提供了底部概率空间的划分，其取值并不影响条件期望的值，只要$P(Y\in \text{subset})$不变，如果两个$Y$提供同样的划分，那么得的条件期望并不变。

1) 条件期望

对一个r.v. $X$，对事件$B$的条件期望是 $$E(X|B)=\frac{1}{P(B)}\int_B X dP$$ 一个r.v.对另一个离散r.v.的条件期望定义为 $$E(X|Y)(\omega)=E(X|{Y=y_n}),\quad \text{ if }Y(\omega)=y_n$$ 一个r.v.对一个B.F.的条件期望定义：$X$是概率空间$(\Omega, \mathcal{F}, P)$上的r.v.，$\mathcal{G}$是一个B.F.，并且$\mathcal{G}\subseteq \mathcal{F}$，那么$X$对$\mathcal{G}$的条件期望为一个r.v.，满足
(i)$\mathcal{G}\text{-measurable}$
(ii)对$\mathcal{G}$中的任意元素$A$有 $$\int_A E(X|\mathcal{G})dP=\int_A X dP$$

2) Conditioning

当Conditioning到另一个r.v.的时候，比如计算$E(X)=E( E(X|Y) )$，第一种看法是根据$Y$的分布，计算各个$E(X|Y)$，另一种看法是把$Y$看成已知，直接算出$E(X|Y)$。

例子：抛硬币，假设正面朝上的概率是$p$，当得到$k$次连续的正面的时候实验结束。计算需要的次数的期望。 令$N_k$为需要的次数，考虑 $$E(N_k|N_{k-1})=N_{k-1}+\left[ 1p + (1+E(N_k))(1-p) \right]$$ 这里是把$N_{k-1}$看成已知，然后观察后面的实验。

不等式

1) Cauchy

$$a_1b_1+a_2b_2+\cdots+\leq \sqrt{a_1^2+a_1^2+\cdots+a_n^2}\sqrt{b_1^2+b_2^2+\cdots+b_n^2}$$ 这个不等式蕴含事实：如果$\sum_{k=1}^{\infty}a_k^2$和$\sum_{k=1}^{\infty}b_k^2$有限那么$\sum_{k=1}^{\infty}|a_kb_k|$有限。

根据这个蕴含关系，二元的时候最简单的关系是线性不等式 $$xy\leq C(x^2+y^2)$$ 从$0\leq(x-y)^2\Rightarrow xy\leq\frac{1}{2}x^2+\frac{1}{2}y^2$所以$C=\frac{1}{2}$

上面不等式诱导$k$个不等式然后相加，单位化后得到两个单位向量$\hat{a}_k^2$和$\hat{b}_k^2$有 $$\sum_{k=1}^\infty |\hat{a}_k\hat{b}_k|\leq \frac{1}{2}\sum_{k=1}^\infty \hat{a}_k^2+\frac{1}{2}\sum_{k=1}^\infty \hat{b}_k^2=1$$ 恢复单位化以前，得Cauchy不等式 $$\sum_{k=1}^\infty \left\{a_k /(\sum_j a_j^2)^{1/2} \right\} \left\{ b_k /(\sum_j b_j^2)^{1/2} \right\} \leq 1$$ 上面的过程说明单位化给出了一种系统的方法从加法不等式到乘法不等式。 单位化后的不等式集合意义是单位向量的点积总小于1。

2) AM-GM Bound

$(x-y)^2\geq 0$展开后用$x, y$的平方根代替$x, y$后有 $$4\sqrt{xy} < 2x + 2y$$ 把$x,y$看成矩形的边，左边是同面积的正方形的周长，右边是$x,y$矩形的周长。

$y=1+x$是函数$y=e^x$切线，而且其图像总在$y=e^x$的图像的下方，即 $$1+x\leq e^x$$ 代入变量替换$x\mapsto x-1$得 $$x\leq e^{x-1}$$ 对$a_k$和$p_k$可得不等式 $$a_k^{p_k}\leq e^{p_ka_k-p_k}$$ $n$个不等式相乘得 $$a_1^{p_1}a_2^{p_2}\cdots a_n^{p_n}\leq e^{\sum p_ka_k-1}$$ 用$a_k/A = a_k/(p_1a_1+\cdots+p_2a_2)$代替$a_k$，不等式的右边变为1，得 $$(\frac{a_1}{A})^{p_1}(\frac{a_2}{A})^{p_2}\cdots (\frac{a_n}{A})^{p_n}\leq 1$$ 两边乘以$A^1=A^{p_1+\cdots+p_n}$得AM-GM不等式 $$a_1^{p_1}a_2^{p_2}\cdots a_n^{p_n}\leq p_1a_1+p_2a_2+\cdots+p_na_n$$

函数空间

紧度量空间$M$上的连续函数构成的空间记为$C(M)$，定义度量 $$d(f, g)=\sup\{|f(x)-g(x)|, x\in M\}$$ 这个度量称为uniform metric，其意义下的收敛是函数序列的一致收敛。

可分是可数的推广，可分空间存在一个可数的稠密子集。

$C[a, b]$中的元素是有限闭区间上的连续函数，有限闭区间上连续蕴含绝对黎曼可积。

向量空间$X$上的两个norm称为等价的，如果存在正实数$\alpha, \beta$对所有的$f\in X$满足 $$\alpha\|f\|_a\leq \|f\|_b \leq \beta\|f\|_a$$ 如果两个norm等价，在一个norm下收敛的序列在另一个norm下也收敛。有限维空间里所有的norm都等价。$(X, \|\cdot\|)$完备的意思是所有的柯西序列收敛称为Banach Space，有限维空间对一个norm完备则对所有的可能的norm完备，因为都等价。

定义$C^n[a, b]$为至少有$n$阶连续导数的函数的空间，其上可以定义norm $$\|f\|_{1,\infty}=\sup_{x\in [a, b]}|f(x)|+\sup_{x\in [a, b]}|f^\prime(x)|$$ 或者 $$\|f\|_{1,1}=\int_{[a, b]}\left\{|f(x)|+|f^\prime(x)|\right\}dx$$ $L^1[a, b]$是$[a, b]$上所有Lebesgue可积函数构成的空间，定义norm $$\|f\|_1=\int_{[a, b]}|f(x)|dx$$ $(L^1[a, b], \|\cdot\|_1)$是banach space，这个norm是类比欧式空间中的坐标norm(坐标差的绝对值的最大值)。
类似欧式距离的范数是 $$\|f\|_2=\left\{\int_{[a, b]}|f(x)|^2dx\right\}^{1/2}$$ Holder's Inequality：$F, G\in L^p[a, b]$，并且$1/p+1/q=1$那么 $$\|FG\|_1\leq \|F\|_p\|G\|_q$$ Minkowski's Inequality：$F, G\in L^p[a, b]$，那么$F+G\in L^p[a, b]$ $$\|F+G\|_p\leq \|F\|_p+\|G\|_p$$ Theorem：如果$1\leq p_1\leq p_2$，那么$L^{p_2}[a, b]\subseteq L^{p_1}[a, b]$，因为 任取$f\in L^{p_2}[a, b]$有 $$\|f\|_{p_1}\leq \|f\|_{p_2}(b-a)^{1/p_1-1/p_2}$$

---

$l^\infty$是无穷序列构成的空间其中的元素满足收敛条件$\sum_{n=1}^\infty x_n^p < \infty$其中$1 \leq p < \infty$。取摸为 $$\|\{x_n\}\|=\sup\{|x_n|\}$$

非闭线性子空间的例子：考虑只有有些个元素非零的序列构成的子集，这个集合是$l^\infty$的线性子空间，而且不是闭的。
Baire Category Theorem

稠密的另一个定义：和任何一个开集都相交。

Baire Category Theorem：如果完备度量空间$X$可以表达成可数个闭子集的并，即$X=\cup_{k=1}^\infty F_k$，那么至少有一个闭子集$F_k$包含一个非空的开集。