MIT 算法导论(3) - 分治法，学习记录

这次整节课都聚焦分治法（Divide and Conquer），分治法不仅在计算机领域应用广泛，甚至在统治和国家治理方面也成效卓越：）讲课老师仍然是Erik Demaine。
分治法的中心思想主要分为三步：

首先将大问题拆分成子问题，直至子问题无法拆分为止（分）；
然后，递归地去求解每一个子问题；
最后，把这些子问题的解，合并成为整个大问题的解（治）。

比如第一课中的 Merge Sort 就用到了该策略，
(1). 将n个元素的数组拆分成两个分别包含 n/2 个元素的子数组，
(2). 递归的使用 Merge Sort 对每一个子数组排序，
(3). 合并两个有序数组，构建出最终排好序的整个数组。

课中总结到，每一个符合分治策略的算法，几乎都有相似形式的递归出现，例如：
Merge Sort 的递归表达式：T(n) = 2T(n/2) + θ(1)
Binary Search 二分查找算法的递归式：T(n) = T(n/2) + θ(1)

接下来课程主要是讲解，如何使用分治算法求解：x ^ n, 斐波那契数列（Fibonacci sequence）以及分治算法在大规模集成电路布局中的应用。

给予一个数字 x 和一个整数 n，求解 x 的 n 次方；

普通求解法是将 x 乘以 n 次，求得最终结果，需要的时间为：θ(n),

分治法求解，x^n =

        x^n/2 * x^n/2 ，如果 n 是偶数；
        x * x^(n-1/2) * x^(n-1/2)，如果 n 是奇数；
  递归表达式为：T(n) = T(n/2) + θ(1) = θ(logn)

斐波那契数列（Fibonacci sequence）也称黄金分割;
Fn =
```
0 , if n = 0
1 , if n = 1
Fn-1 + Fn-2 , if n >= 2 
```
- 普通递归求解法，其时间复杂度为：O(golden_ratio^n)，golden_ratio = (1+sqrt(5))/2，该解法非常慢，时间耗费是指数级规模；但是我们想要的是多项式复杂度的算法，因为任何以多项式级为上限的算法都是好算法；
- 自下而上的递归解决算法，Bottom-Up Algorithm，核心思想就是，用内容缓存的方式来处理Fib已经计算过的值，假如某些值被计算过了，就直接返回并使用它；采用缓存对普通求解法进行改造后，计算时间是线性与 n 相关，时间复杂度变成：θ(n)；
- 朴素平方递归式，该方法可以更好地求解Fb问题，但是由于各种原因，这种方法实际上不能实现；
- 平方递归算法；
  定理：(Fn+1 Fn) = (1 1)^n
```
      Fn    Fn-1      1 0
```
  主要是通过计算矩阵的 n 次幂来得到Fn；其中矩阵乘法，主要讲解了著名的施特拉森算法; 一般矩阵乘法的时间复杂度为O(n^3)，施特拉森算法因为只有每次的分治法，只有七个矩阵乘法运算，所以依照主定理可以得出时间复杂度为 O(n^2.807)，成功地将复杂度的次方降低到3以内。
大规模集成电路节点布局；
这部分Erik用了很大一部分时间来讲解，给予一定数量的电子电路芯片，如何才能在占用更小面积的条件下，将他们放置到集成电路面板上。主要还是采用了二叉树的思路，
只是这次不是一份为2，而是一分为4，得到的递归公式为：L(n) = 2L(n/4) + θ(1) = θ(sqrt(n)) = θ(n^1/2)

整堂课，主要还是讲解分治法的原理，及其在算法上的应用。其实了解分治算法的思想非常重要，算法导论的后面很多章节都会用到它。

下面是我实现的求 x^n 和 Fib 的代码片段，仅供参考：

// 普通乘积法求 x^n
// O(n)
func normalXPower(x, n int) int {
    total := 1
    for i := 1; i <= n; i++ {
        total *= x
    }
    return total
}

// 分治法求 x^n
// O(lgn)
func divideConquerXPower(x, n int) int {
    if n == 1 {
        return x
    }
    if n%2 == 0 {
        return divideConquerXPower(x, n/2) * divideConquerXPower(x, n/2)
    } else {
        return divideConquerXPower(x, (n-1)/2) * divideConquerXPower(x, (n-1)/2) * x
    }
}

var fibCache = make(map[int]int)

// 普通递归解法
// Ω(Ψ^n), Ψ=(1+sqrt(5))/2
func Fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return Fib(n-1) + Fib(n-2)
}

// 从下而上的缓存递归解法
// θ(n)
func FibBottomUp(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    if _, ok := fibCache[n]; ok {
        return fibCache[n]
    } else {
        rt := FibBottomUp(n-1) + FibBottomUp(n-2)
        fibCache[n] = rt
        return rt
    }
}

以上代码我已经放到 github，如有需要请点击这里。

第3讲视频地址