东海闲湖城湖景房:《算法设计与分析基础》笔记2

第6章 变治法

预排序：用于下列场景，检验数组中元素的唯一性，查找数组中出现次数最多的元素，等等

高斯消去法：将矩阵变成一个上三角阵，然后从最后一个方程开始，反向替换得到原方程的解。
为了减少舍入误差，每次选取第i列系数绝对值最大的行，并且与当前行交换。

LU分解：高斯消去法得到的上三角阵为U，在消去过程中行的乘数构成了下三角阵L（假设不存在行交换的情况下）。比如，在消去第i列的时候，把第i行乘以a加到第j行上，那么U[j][i] = -a。如果存在行交换的话，那么L也要做相应的交换。可以证明 A=LU
那么方程组Ax=b就等价于 LUx=b。
假设y=Ux，那么Ly=b，因为L是下三角阵，所以容易求出y。
Ux=y，所以也容易求出x。
优点：只需做一次LU分解，然后对所有的b都可以求解。

计算矩阵的逆：AX=I
假设逆矩阵的第j列为Xj, I的第j列为ej。
那么原方程便等价于求n的方程组 A * Xj = ej
可通过LU分解来求。

计算行列式：高斯消去法的每一步，要么改变行列式的符号，要么将行列式乘上一个常量，要么不变。最终得到一个上三角阵，三角阵的行列式等于对角元之积。所以容易推得原行列式的值。

AVL树：是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左右子树的高度差，这个因子要么为0要么为1或-1。 （注意：并不只是根节点满足这个特性，所有节点要都满足）

将一个节点插入AVL树，可能导致失去平衡，某些节点的平衡因子变成了2或－2。通过旋转操作来回复平衡。旋转分为四种R（右旋），L（左旋），LR（先对节点r的左子树左旋，然后将以r为根的树右旋），RL。在插入节点后，先找到最靠近插入节点的不平衡节点，然后旋转以该节点为根的树。




2-3树：节点分为两种，2节点－－包含1个元素和2个儿子，3节点－－包含2个元素和3个儿子，儿子可以为空。所有的叶子都必须在同一层。
总是将新的键插入到叶子里，如果叶子中的键变成了3，那么将中间的键移至父节点，并且该叶子分裂成了两个节点。分裂过程可能一直向上进行。

堆和堆排序：略

霍纳法则：对多项式 p(x) = an*x^n + a_(n-1)*x^(n-1) + ... + a0进行求值。也可用来进行求幂运算。
#Horner(p[0 .. n], x
#  r = p[n] //p[n]为x的n次项的系数
#  for(i=n-1; i>=0; i--)
#    r = x*r + p[i]
#  return r

计算图中的路径数量：假设图的邻接矩阵为A，那么A^k中的元素A^k[i,j]表示了从顶点i到顶点j存在多少条长度为k的路径。

第七章 时空权衡
计数排序：用于数组元素在一个有限范围内的情况。略。

字符串匹配的Horspool算法：在长度为n的文本中寻找某个长度为m的子串（模式）M。根据和模式最后一个字符对齐的那个字符来决定将模式向后移动的距离。假设文本中的这个字符为c，那么移动的距离为：
t(c) = m (if c 不再模式的前m-1个字符中）
t(c) = 模式中前m-1个字符中最右边的c到模式尾部的距离 (else)
最差效率为O(mn)，对随机文本而言，效率为O(n)
#shiftTable(p[0 .. m-1])
#  initialize table with m
#  for(j in 0 .. m-2) do table[p[j]] = m-1-j
#  return table

字符串匹配的Boyer-Moore算法：同上面的算法类似，但是不光考虑最后一个位置。假设模式的最右边k个字符已经匹配上了，而第k+1个字符不匹配。
a）那么根据不匹配的字符来确定的移动距离为 d1 = max{ t1(c)-k, 1}
其中t1(c)为Horspool算法中的t(c)
b）也可以根据匹配的k的字符来确定移动距离d2。假设模式中最后的k个字符组成字符串suff(k)，如果模式中还存在这样一个字符串，那么只要移动到最右边的这样一个字符串。如果模式中不存在令一个suff(k)，就找出模式中最长的前L个字符组成的前缀，使得该前缀等于suff(L)。
总是选择a和b中最大的距离来移动。
if(k==0) d = d1; else d = max{ d1, d2 }

闭散列（开放寻址法）：用循环数组还存放。冲突的解决：插入时，若该位置已经被占，则向后移，直到找到一个空位；删除时，不能简单地将该位置清空，而应放置一个标记。 双散列法：遇到冲突时，并不是向后移动一个位置，而是每次移动s个位置，s是根据另一个散列函数S计算出来的，假设键为K，则s＝S(k)，移动距离为s, 2s, 3s, ...

B树：1)根要么为叶子，要么有2到m个子女 2)内部节点具有ceil(m/2)到m个子女 （也就是具有ceil(m/2)-1到m－1个键） 3)所有叶子都在最底层。 m称为B树的次数。 操作类似2-3树。m=2时称为2-3-4树