编程珠玑系列笔记 -- 第二章 啊哈！算法

Posted on | Post modified: | In |
Words count in article: 1,762

本书的另一个中心思想显而易见：良好的算法是程序性能提升的关键。

下面还是通过探讨几个实例，来领会一下算法的重要性。

三个问题

A. 给定一个最多包含 40 亿个随机排列的 32 位整数的顺序文件，找出一个不在文件中的 32 位整数(在文件中至少缺失一个这样的数 - - 为什么? )。在具有足够内存的情况下，如何解决该问题?如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题?

至少缺失一个这样的数是因为：32 位无符号整数的表示范围是0 到 4,294,967,295，比 40 亿大：。如果有足够的内存，可以采用第一章的位图表示法，需要的内存是：4 000 000 000/8 = 500 000 000，500MB 的内存。而且我们需要使用二分查找来加速查找过程，顺序遍历 500MB 的空间是很慢的。使用二分查找对这种量大的数据集是非常重要的手段，但 二分查找的基础是数据集有序。所以初看这里是没法直接使用二分法的，但是如果我们这样想：32 位整数的每一位不是 0 就是 1，我们按照第 1 位划分的话，就可以划分出两个集合（需要遍历全部数据一遍），如果某个集合小于 $2^{31}$ 个数就选中成为我们下一次划分的对象（如果两个集合都小于 $2^{31}$ 就随便选一个），直到我们得到一个空集，而这个空集中本来应该存在的那些数，就是缺失的数了。在划分集合的时候，我们实际上要把数据存到硬盘中，可以使用 buffer 来减少 IO 次数。最坏时间复杂度是一个等比数列：
$$n+\frac{1}{2}n+\cdots+1 = 2n$$

可见这里的二分法并没有起到logN的效果。需要遍历的二分法还算什么二分法呢？但庆幸的是，我们至少可以解决这一题。

B. 将一个 n 元一维向量左旋转 i 个位置。例如，当 n=8 且 i=3 时，向量 abcdefgh 旋转为 defghabc。简单的代码使用一个 n 元的中间向量在 n 步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于 n 的时间内完成向量的旋转？

方法 1：将前 i 个元素复制到一个临时空间，余下的 n-i 个元素向左移 i 个位置，最后将最初的 i 个元素从临时空间复制到 x 中余下的位置。时间复杂度：2i+(n-i)=n+i，也就是 O(n)；空间复杂度：i，也就是 O(n)。

方法 2：使用类似方法 1 的办法，但只使用一个元素大小的临时空间，每次只移动一位，总共需要移动 i 次。时间复杂度：(n+1)*i，也就是 O(n^2)；空间复杂度：O(1)。

方法 3：杂技算法。第一步：移动x[0]到临时变量 t，然后移动x[i]到x[0]，x[2i]到x[i]，依此类推（将 x 中的所有下标对 n 取模），直至返回到取x[0]中的元素，此时改为从 t 取值然后终止过程。第二步：如果该过程没有移动全部元素，就从x[1]开始再次进行移动（执行第一步的算法操作），直到所有的元素都已经移动为止。

这个算法的核心思想应该是这样的：将该数组序列看成是一个环状队列，每次执行第一步的算法都可以使一组元素落到它们最终的位置上，而又不影响到其它元素。

第二步执行的次数是GCD(n,i)（n 和 i 的最大公约数）。这样一来我们就不用记录元素是否移动过这个状态了，直接就可以知道循环多少次。

该算法的时间复杂度：n+GCD(n,i)，也就是 O(n)。空间复杂度：O(1)。

这个算法虽然表现不错，但是不便于理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>

using namespace std;

int gcd(int a, int b){
    return a%b?gcd(b, a%b): b;
}

int a[20];
void acrobat(){
    int n=20, i=6;
    int temp;
    for(int j=0;j<gcd(n,i);j++){
        temp = a[j];
        int count=0;
        while(1){
            if(i*(count+1)%n == 0){
                a[j+i*count%n] = temp;
                break;
            }else{
                a[j+i*count%n] = a[j+i*(count+1)%n];
                count++;
            }
        }
    }
}

int main()
{
    for(int i=0;i<20;i++){
        a[i] = i;
    }

    acrobat();

    cout << "out" << endl;

    for(int i=0;i<20;i++){
        cout << a[i] << endl;
    }
    return 0;
}

方法 4：递归算法。旋转向量 x 其实就是交换向量 ab 的两段，得到向量 ba。这里 a 代表 x 中的前 i 个元素。假设 a 比 b 短，将 b 分为$b_l$和$b_r$，使得$b_r$具有与 a 相同的长度。交换 a 和$b_r$，也就将$ab_l b_r$转换为$b_r b_l a$。序列 a 此时已处于其最终的位置，因此现在的问题就集中到交换 b 的部分。由于新的问题与原来的问题具有相同的形式，我们可以递归解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//分别从i和j位置开始，交换k个元素
inline void swap(int a[], int i, int j, int k){
    for(int p=0;p<k;p++){
        int temp = a[i+p];
        a[i+p] = a[j+p];
        a[j+p] = temp;
    }
}

//从i位置开始，处理左leni，右lenj的旋转
void first(int a[], int i, int leni, int lenj){
    if(leni == lenj){
        swap(a, i, i+leni, leni);
        return;
    }
    if(leni<lenj){
        swap(a, i, i+lenj, leni);
        first(a, i, leni, lenj-leni);
    }else{
        swap(a, i, i+leni, lenj);
        first(a, i+lenj, leni-lenj, lenj);
    }
}

方法 5：三次翻转: $(a^r b^r)^r = ba$。从 ab 开始，首先对 a 求逆，得到$a^r b$，然后对 b 求逆，得到$a^r b^r$。最后对整体求逆，得到$(a^r b^r)^r$，此时恰好就是 ab。

1
2
3
reverse(0, i-1) /* cbadefgh */
reverse(i, n-1) /* cbahgfed */
reverse(0, n-1) /* defghabc */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//从i位置开始，到j位置结束(包含j)，翻转这一段的a中的元素
inline void reverse(int a[], int i, int j){
    for(int k=0;k<(j+1-i)/2;k++){
        int temp = a[k+i];
        a[k+i] = a[j-k];
        a[j-k] = temp;
    }
}

//i位置是b段的开始，总长度n
void res(int a[], int i, int n){
    reverse(a, 0, i-1);
    reverse(a, i, n-1);
    reverse(a, 0, n-1);
}

C. 给定一个英语字典，找出其中的所有变位词集合。例如，“pots”、“stop”、“tops”互为变位词，因此每一个单词都可以通过改变其他单词中字母的顺序来得到。