Algorithms Fourth Edition 学习记录

关键词：算法
作者：BIce 创建时间：2012-10-16 20:25:41

       之前听说过这本《Algorithms》是本很经典的书，正好也想看看英文书，就买下了这本书的第四版，经过一个月的阅读，发现本书确实十分经典。我甚至怀疑之前学算法的时候看的那些书我是怎么坚持下来的。本书选取了几乎所有基本数据结构以及常用的算法，并以Java语言进行了细致的实现，每个算法的实现都十分简练、精彩，思想的讲解也十分到位，十分佩服本书的作者哇，膜拜orz.. 在大致看完一遍的基础上，简单的对本书的学习进行下总结吧，以后一定会再次阅读的～

       《Algorithm》第四版大致分为六个部分，也就是本书的六个章节，下面对这六个部分进行简单记录。

1 Fundamentals

  1. 本章作为介绍性的章节，主要在Java语言基础上对编程的主要概念进行解释，包括：数据抽象、数据类型、基本的Java语法和元素。
  2. 基础的集合类：Bags，Queues和Stacks的介绍和实现（Array和Linked List两种）。
  3. 基本的算法分析：时间与空间复杂度的分析方法介绍。
  4. Union Find：通过引入了Union Find的问题，给出了集合的树形表示及合并操作的形式，并引入了平衡树的概念及Union Find的平衡树版本。

2 Sorting

本章主要介绍了基本的排序算法，主要包括：

  1. Selection Sort.

每次选取一个最大（最小）元素放到指定位置，对剩余的元素集做重复动作直至全都放好。时间为O(N*N)，空间为1，稳定性不具备。（基本不用）

  1. Insertion Sort.

从左向右，每次向已排序好的数组中加入一个元素（初始只有一个元素），直至全部加入。时间为O(N)~O(N*N)，空间为1，具备稳定性。

  1. Shell Sort.

Insertion Sort的改进版，为了减少Insertion Sort的移动距离。每次选取所有第h个（0,h,2*h…为一组，1,h+1,2*h+1…为一组，…，h-1.2*h-1…为一组），分组进行排序(叫做h-sorted)，每次循环对h进行减少，直至h为1，排序完成。

  • h值的初值计算以及减少方式称作Increment Sequence，它可以采取不同的计算方式，书中算法给出的计算方式为：

h初值：h=1; while (h<N/3) h=3*h+1;

h减少：h=h/3;//循环减少直至1

  • 另外，对于h个需排序子数组进行排序，子数组内部使用Insertion Sort，外部可以通过一个从h到N的循环来整合完成，十分简洁：

while(h>=1){

       for(int i=h;i<N;i++){

              //针对每个元素i（小于h部分是子数组头，不用处理），查看其从属的子数组，进行Insertion Sort

       for(int j=i; j>=h && less(a[j], a[j-h]; j-=h)

              exch(a,j,j-h);

       }

       h=h/3;

}

       时间O(N*logN)，空间1，不具有稳定性。

  1. Merge Sort.

将数组分为两部分，然后递归对子数组进行排序，排序完成后将两个子数组Merge会一个整体排序的数组。（自顶向下）

  • Merge Sort中拆分出的小数组（长度小于15），可以使用Insertion Sort代替递归，减少递归树高度。
  • 自下向上的Merge Sort：将数组拆分成大小为sz的子数组集，相邻两个数组合并，得到大小为sz=sz*2的子数组集，重复合并过程，直至sz大于等于N。

具有稳定性，时间O(N*logN)，空间N。（Java默认对元素为引用类型的元素使用此种排序）

  1. Quick Sort.

先将待排序数组进行无序化（随机调整顺序，防止已经排序的数组导致Quick Sort时间效率达到O(N*N)），使用第一个元素进行划分(Partition)，找到其应该所在的位置，递归对剩下的两部分进行Quick Sort过程。

  • 优化方法：子数组小的使用Insertion Sort；不使用第一个元素，从数组中选取几个（3个）数，取中间的作为Partition的key。
  • 针对一个值全都一样的数组，排序需要O(N*N)，（因为调用递归树每次只化成1和N-1的两个子树，递归高度是N）。针对这种情况（有重复值比较多），作者给出了一种3-way Partition的方法，思想就是在计算Partition的时候(从lo～hi)，将与key相等的元素一起都计算出来，放到应该的位置（如从lt到gt），然后递归时只对lo~lt-1和gt+1~hi进行递归Quick Sort即可。（Java默认对元素是原始类型的使用此种排序）

时间O(N*logN)，空间logN，不具有稳定性。

  1. Heap.

Heap在本书中的主要用法是用来实现优先级队列（Priority Queues），它的常用操作有两个：RemoveMax和Insert。其基础是一个完全二叉树（可以用数组来维护它的信息），Heap要求每个节点都不小于（不大于）它的子节点。它的典型操作有两个：

  • Swim：当新的Node加入Heap时（加入尾部），需要对此节点进行一个向上传递的操作，与其父节点进行比较，如它更大则与父节点交换，持续比较直到找到比它大的父节点。
  • Sink：当执行RemoveMax的操作时，需要把根节点删除（与最后一个元素进行交换），然后对新的根节点执行Sink操作：找到它比较大的子节点，与之交换，持续向下直至没有比它大的子节点。
  • 构建堆的过程可以是一个持续的加入节点然后Swim的过程，也可以是一个先按顺序构建好树，然后从第N/2个节点开始执行Sink的过程（直至1）。

不具有稳定性，时间O(N*logN)，空间1。

3 Searching

       本章认定的Search问题，是在一个Symbol Table中进行的元素查询，Symbol Table的元素内容为key=>value对。本章考虑了三种Symbol Table的实现：Binary Search Tree，Red - Black Tree，(BST和RB-BST都是有序表)，Hash Table（无序）。

  1. Binary Search Tree

二分查找树，二叉树的一种，每个节点都大于左子树中所有节点的Key，小于右子树的节点的Key。（像是Quick Sort的形式）。BST中序遍历即为有序访问。（树形式与加入节点的方式有关）

  1. Red – Black Tree

作者在提出Red – Black树之前，首先提出了一个2-3树的概念。

  • 2-3树，即允许一个节点可以有两种形式，一是基本的二叉树节点，二是可以有两个Key，三个子节点，的树节点。由两个Key来划分自身与子节点之间的关系。（左边小于两个Key的子树，中间在两个Key之间的子树，右边是大于两个Key的子树）。作者给出了关于2-3树的插入、删除等操作的方式，保证了这种2-3树一种平衡树（具体操作见书）
  • 而Red – Black Tree其实就是用标准的BST实现2-3树的一种形式，它将3-node以两个BST 2-node表示。假定一个3-node的Key为a,b(a。这样可以由BST表示为a是b的左子节点，其中小于a的部分作为a的左子树，a,b之间的作为a的右子树，大于b的部分为b的右子树。而这种a与b之间的边即被称为Red边，其余的则是Black边。
  • Red - Black Tree的操作与2-3树的类似，就是2-3树操作的BST版本翻译。而Red – Black Tree可以保证Perfect Black Balance：从根节点到任意叶子节点经历的黑边数相等。（Java中TreeMap的实现即为此）
  1. Hash Table

Hash Table要解决的问题首先有两个：Hash Function的定义及Collision-Resolution方案。其中：

  • Hash Function的定义要根据Hash Key的不同而选取不同方案。
  • Collision-Resolution方案有两种：Separate Chaining（冲突向后拉表）和Linear Probing（线性探测）。（Java中的HashMap使用的Separate Chaining方式）

缺点：Hash Function的计算可能很费时，需要针对输入设计不同的方案，对于有序的查询操作支持比较难实现。

4 Graph

  1. Undirected Graph
  • DFS：递归形式
  • BFS：队列形式
  • Shortest Path：BFS访问长度即为最短路径
  • Connected Components：连通子图计算，对每个顶点进行DFS计算，记录count值，每次顶层成功执行DFS时增加，每个顶点记录自己被访问时的count值。值相同的为一个连通子图。
  • Cycle Detection：环检测，思想：如果有环，则与环有连通性的任意一个节点，到环的任一个顶点，肯定有两条以上的路径。则方法：在对图中任意一点v进行DFS的过程中，v的邻接节点中有之前访问过的节点w（不是v的前一个节点），则说明从某个顶点s到w有经过v和不经过v两条路径，则有环。
  1. Directed Graph
  • Cycle Detection：记录进行DFS过程中的调用栈，如果在某节点v的邻接节点有w，w已经被访问过，且在调用栈中，则找到了另一条到w的路径，有环。
  • Directed acyclic graph(DAG)：有向无环图，可以进行拓扑排序。
  • DAG上的Topological Sort(拓扑排序)：对图进行DFS，记录每个节点完成DFS的顺序，反向输出即为拓扑排序结果。
  • Strong Connectivity：以拓扑排序的结果执行DFS，记录count，即可。
  1. Minimum Spanning Trees

针对Undirected Edge-weighted Graph。基本方法有两个：

  • Prim’s algorithm：在每次向生成树中加入一个新边来完成（最小权重的不会产生环的边），保证一直都是一棵树。
  • Kruskal’s algorithm：从v个单节点的子树开始，选能连接两个子树的边连接（最小权重的不会产生环的边），直至变成一棵树。
  1. Shortest Paths

针对Edge-weighted Digraph（有向有权重图）。情况分为：有无负边

无负边的情况（可有环）：

  • 重要的操作：Edge relaxation，针对边v->w，查看distTo[v]+e.weight与distTo[w]大小，更新distTo[w]的值和edgeTo[w]的值。
  • Vertex relaxation：针对顶点v的所有邻接边，执行edge relaxation。
  • Dijkstra’s algorithm：向SPT（Shortest Path Tree）中加入具有最小distTo[]值的顶点v，删除之，并对此顶点v进行relax更新distTo值。

有负边的无环图：

  • 以拓扑排序的顺序进行顶点的relax，可以在线性时间得到单源点最短路径。（可以处理负边，通过边变负可以计算最长路径，不同的起点s，distTo[s]=0即可）
  • Critical Path（关键路径计算）：在图中加上虚拟初始节点，和虚拟结束节点，对任务的执行拆分成开始和结束两个节点，边长为任务时间。对图计算最长路径即可得到关键路径。

有负边有环图：

  • Bellman-Ford algorithm：算法为relax所有的边，重复执行V次。

for(int pass=0;pass<G.V();pass++){

        //relax all Edges

      for(int v=0;v<G.V();v++)

              for(DirectedEdge e:G.adj(v))

                     relax(e);

}

书中使用基于队列的Bellman-Ford算法，即为用一个FIFO的队列来记录在上次Pass中distTo有修改的节点。仅处理有修改的节点进行relax，这样就可以减少不必要的操作。

  • 负环检测：如果在执行V Pass之后，上述用于记录distTo改变顶点队列仍不为空，则说明当前图中有负环，且负环就存储在edgeTo[]中。

5 Strings

       本章主要针对String类型的特殊算法和存储进行了介绍，String中字符属于Alphabets中。

  1. String Sort

讨论针对String字符串为Key的排序问题。

  • Key Indexed Sort：记录每个可能的Key的出现次数，这样排序时直接就可以根据Key的相对位置放置元素。在Key的范围比较小的时候很好用。
  • LSD(least significant digit) Sort：针对长度一致的字符串Key，从右向左，每一位的字符进行Key Indexed Sort，直至最左边。要求Key Indexed Sort会保持稳定性。本身具有稳定性。
  • MSD（Most significant digit）Sort :可以处理长度不同的字符串Key排序。从左向右，依次处理每一位，进行Key Indexed Sort，然后针对剩余的字符串数组（本位相同），分别递归进行MSD Sort。（其实现书中给出的极其复杂）。最坏情况为所有字符串都相同。具有稳定性。
  • Three-way String Quicksort：MSD的一种变形，与3-way quick sort类似的想法，每次不是将数组划分为~R个（符号表大小）子数组，而是每次将数组划分为3个子数组，按照a[lo]的d位字符v进行划分，分为d位字符小于v，等于v，大于v，三个区间。分别递归排序。用以解决MSD在公共字符多时（字符串都相同）会出现的线性性能的最坏情况。不具有稳定性
  1. Tries

可支持针对String Key进行的前缀查询，可用于保存符号表（以String为Key的符号表）。

  • 基本形式为一个多叉树。（子节点数为字符表的大小R）。每个节点拥有R个指针，用于指向字符串后续的字符节点。节点有一个Value用于存储实际值，Value为null则是中间节点，没有实际的值。
  • Ternary Search Tree：三元查找树，Tries的一种变形，与3-way quick sort类似，是一种压缩方式。每个节点的子节点数有R个变为3个，存储值字符Key，其中left指向其同层的小于它的Key的字符串，middle指向以Key为开头的字符串，right指向同层的大于它的Key的字符串。（形象的话，将left和right拉平，middle向下，和Tries的原始形式是一样的）
  1. Substring Search

问题：在一个长度为N的字符串中，查找长度为M模式子串出现的位置。（未出现返回负数）。在本节的讨论过程中，假定M值较小，N值较大。（N远大于M）

  • KMP Algorithm（Knuth-Morris-Pratt）：本质上KMP算法是基于一个针对pattern string的有限状态机。通过对Pattern的分析，我们可以计算出当在Pattern某个位置j的对比过程中出现mismatch的时候我们可以选择的合理回退值对j进行修改。

计算状态机的方式如下：dfa[R][M]

dfa[pat.charAt(0)][0]=1;

for(int X=0,j=1 ;j<M ;j++){

      for(int c=0;c<R;c++){

            dfa[c][j]=dfa[c][X];//DP？

      }

      dfa[pat.charAt(j)][j]=j+1;

      X=dfa[pat.charAt(j)][X];//X是当前位置j出现mismatch时的回退状态，在本处match之后，X也要做相应的状态变化来进行下一个j的处理。

}

  • Boyer-Moore Substring Search：与KMP类似，不同的是从右向左扫描pattern（匹配还是自左向右进行），进而计算在右端不匹配时需要移动的位置。（细节见书）
  • Rabin-Karp fingerprint search：使用Hash函数计算pattern的hash值，然后取字符串中长度相同的子串进行hash值计算，如果相同再继续执行具体匹配。本方法的难点在于Hash函数的快速计算。（书中给出了一种可以由前一个子串hash值快速计算出后一个连续子串hash值的方法）
  1. Regular Expressions

与NFA等价，没有细看，下次补上。

  1. Data Compression

主要讲了二进制数压缩以及Bitmap的压缩。

  • 字符串Huffman 压缩：根据使用频率，对字符串进行不同长度的编码，使用Trie来表示。构建Trie的过程可以视为对一个MinPQ进行树节点合并直至一个的情况。

6 Context

       本章主要讲了一些扩展性的东西，如Event-Driven Simulation啦，B-Tree啦，Suffix array啦，网络流算法啦等等。这些我只简单扫了一眼，为保持下次阅读还会有兴趣的新鲜感。恩以后保持这个习惯~

留言功能已取消，如需沟通，请邮件联系博主sunswk@sina.com，谢谢:)