求道生而为龙

看完编程珠玑第二章，发现确实很好玩。第二章用三道题目引出三个基本操作，然后再将这三个操作推广到更一般的情形。

1. 二分搜索：将线性搜索的O(n)时间降到O(log2n) ，要求单调
   1. 看这句话似乎很平凡无奇，但是这句话确实是二分搜索适用范围的精确表达，关键在于线性搜索四个字。你明确知道什么样的是线性搜索么？我不敢说我很明确，但是在这里我把它总结为在线性解空间里寻找解。曾经有人给我讲过二分枚举法，一个奇形怪状的容器，问水面多高的时候水是总容积的一半。这就是个线性有序的解空间，可以进行二分搜索。如果你可以求得高与体积的关系式，那么直接根据一半体积求高的做法就更像是hash查找。
   2. 二分搜索的核心问题：1.有序2.有个比较“大小”的方法来将解空间每次减半（定义一个范围，在该范围内表示元素的方式，确定哪一半范围存在缺失整数的方法）
   3. A问题，有一个连续的文件里面有40亿个32位整数，找出至少一个不在这个文件里的32位整数。朴素的二分思想，每次找出存在缺失整数的那一堆。
2. 向量旋转：问题B：用几十个字节的额外空间将一个n元向量x在正比于n的时间内左旋i个位置。对应于实际问题中交换相邻的不同大小的内存块。
   可用方法：
   1. “杂技”算法。以“元素”为单位（元素不仅可以为数组元素，还可以为一切旋转单位），循环移动该向量中的元素，若元素个数为n，移动距离为d，那么需要移动n与d的最大公约数趟。
   2. 等大小内存块移动法。目的：ab->ba，假设b比a长，那么取b后面的与a等长的一段br，与a交换。于是效果就是ablbr->brbla，a已经到了最终位置，剩下的目标就是交换bl和br。递归操作。
   3. 求逆法。(a’b')’＝ba
      reverse(0, i-1);     //abcdefgh->cbadefgh
      reverse(i-1, n);     //cbadefgh->cbahgfed
      reverse(0, n);       //cbahgfed->defghabc

   直观上比较，杂技算法对每个元素仅存取一次，而求逆要两次，那么杂技算法算法的速度要两倍于求逆。实际上当n比较大而旋转距离变长的时候，由于杂技算法的高速缓存性能比较差，而求逆大部分操作为顺序读取，由于缓存局部性的影响，杂技算法的实际表现并不如求逆算法。

3. 标识：当使用等价关系来定义类别时，定义一种标识，使得类中每一项都具有相同的标识，而该类以外的其他项没有，这样就可以将一个感觉无从下手的问题变成一个用已知数据结构和算法解决的问题。（ps：后续还可以根据标识进行排序，二分等等操作）
   问题C，挑选出一个词典中所有的变位词，就是如deposit和topside这样关系的词。如果要考虑单词字母的所有排列，那是注定要失败的方法。因为算法复杂度实在太大了。注意描述，deposit和topside是一类，他们是变位词，也就是说他们存在着某种等价关系。只要给所有变位词定义上同样的标识，然后将其按照标识排序，这个问题就变成了一个很容易下手的问题。

后记：本章主题是寻找合适的算法，绝对不要有了想法就急不可耐的去实现，就是要找到自己的灵机一动，用巧妙的方法来实现，要“建设性的懒惰”。

This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.