Raymond's Cabin

for sharing thoughts

0%

分而治之算法 Divide and Conquer

Posted on Valine:

分而治之算法是 MapReduce 方法的基石，是数据挖掘的核心。

分而治之的本质是：

  1. 将大的问题分成两个以上小的问题
  2. 分别解决每个小问题
  3. 将各小问题解答组合起来，得到原问题的解答

拆分出来的小问题通常与大问题相似，因此可以通过递归解决。

非递归：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
template<class T>
bool MinMax(T w[], int n, T& Min, T& Max)
{// Locate min and max of w[0:n-1].
 // Return false if fewer than one element.
 // special cases, n <= 1

    if (n < 1) {
        return false;
    }

    if (n == 1) {
        Min = Max = 0;
        return true;
    }

    // initialize Min and Max
    int s;  // start point for loop
    if (n % 2) {  // n is odd
        Min = Max = 0;
        s = 1;
    } else {  // n is even, compare first pair
        if (w[0] > w[1]) {
            Min = 1;
            Max = 0;
        } else {
            Min = 0;
            Max = 1;
        }
        s = 2;
    }

    // compare remaining pairs
    for (int i = s; i < n; i += 2) {

        // find larger of w[i] and w[i+1]
        // then compare larger with w[Max]
        // and smaller with w[Min]
        if (w[i] > w[i+1]) {
            if (w[i] > w[Max]) {
                Max = i;
            }
            if (w[i+1] < w[Min]) {
                Min = i + 1;
            }
        } else {
            if (w[i+1] > w[Max]) {
                Max = i + 1;
            }
            if (w[i] < w[Min]) {
                Min = i;
            }
        }
    }

    return true;
}

应用

由分而治之算法衍生出来的算法，常用的有归并排序和快速排序两种。

解决线性代数的矩阵乘法，可以使用分而治之算法。

分而治之算法可以应用到很多生活场景，比如求解递归方程、找出伪币、找最轻和最重、得出距离最近的点对等。