TAOCP读书笔记——Search(1)

        最近抽时间在读高爷爷的《计算机程序设计艺术》这本书，没敢看英文原版，找了中文版的来读，顺手做了一些笔记。先看的查找部分，从最简单的顺序查找开始，基础不好，跳过大部分数学分析部分。。。

 

1. 排序有时是查找的一个好替换，而查找有时又是排序的一个好替换。

    举例来说，给定两组数 A={a1, a2, a3, ... am}和 B={b1, b2, b3, ..., bn}，确定是否A包含于B。这本身有三种解法，即：

    1) 顺序地把每个ai同诸bj做比较知道找到一个相同的为止。

    2) 把A和B排序，然后通过这两个文件的一个序列，校验适当的条件。

    3) 把B记录入一个表，然后查找每一个ai。

    上述每一种解法，在m和n的不同范围内都是有吸引力的。对于某个常数c1，解法1将花费大约c1*m*n个时间单位，而对于某个(更大的)常数c2，解法2将花费大约c2*(m*lg m+n*lg n)个单位时间，对于某个(仍然很大的)常数c3和c4，使用一个适当的散列方法，解法3将花费大约c3*m+c4*n个单位时间。对于很小的m和n，解法1是好的，但当m和n增大时，解法2很快变得更好。最后解法3编程可取的，直到n超过了内存大小为止，然后解法2又变得优越，直到n变得非常大为止。

      由此可见，所谓最优的算法是有前提条件的，在数目较小的情况下，常数项也是要考虑的东西。

 

2. 从起点开始往下查，直到找到了正确的键码为止，然后停止——顺序查找。

      最为普通的顺序查找时间消耗平均值是(N+1)/2，但是方差非常的大，到达了0.289N。

      重要的加速原理：当程序中的一个内循环要测试两个或多个条件时，则应该力图将测试减少为只有一个条件。

      在这样一个简单的顺序查找中，也有很多的因素需要考虑，其中一个方面就是“存取频率”。我们分析时一直假定每个变元都以同样的频率出现，这并不是一个显示的假定。

      一个“自组织”的文件——每当一个记录被成功地定址时，便把它移动到表的开头。这是一种有效的方法。

 

3. 内插查找。人们手翻字典的例子，对“大得多”和“稍微大一点”进行区分——当知道K介于Kl 和Ku 之间时，把下次探查的位置选在位于l和u之间在大约(K-Kl)/(ku-kl)这一点上（假定所有键码都是数值形式的）。

      对于二分查找来说，它会把查找工作量从n降低到n/2，而理论上，内插查找则把n降低到根号n。因此平均来说，内插查找花费lglg N步。

      然而内插查找需要很多额外的计算，再加上典型的文件并不充分的随机，因此效果并不明显，在查找可能很大的外部文件的早期阶段时才最为成功。

 

4. 有一个关于二分查找的小优化——比如内存方面，记录当前位置i和它的变化速度s，每次不相等的比较之后，可以置i=i+-s和s=s/2。除此之外在二分查找中使用了较多的除法，而如果使用加减法代替的话，就可以有一定的优化作用，比如斐波那契查找，就只使用加减，而不用除法。