分治策略-基础.md

基础思想

分治策略(Divide and Conquer)基本思想：

1. 将原始问题划分或者归结为规模较小的子问题；

2. 递归或迭代求解每个子问题；

3. 将子问题的解综合得到原问题的解。

注意：

1. 子问题和原始问题性质完全一样；（递归基础）

2. 子问题之间可彼此独立地求解；

3. 递归停止时子问题可直接求解。

问题

二分搜索

算法 Binary Search(T, l, r, x)

输入：数组$T$，下标从$l$到$r$；数$x$

输出：$j$ // 若$x$在$T$中，$j$为下标；否则为$0$

伪代码：

l ← 1; r ← n
while l <= r do
    m ← ⌊(l+r)/2⌋ // m为中间位置
    if T[m]=x then return m // x是中位数
    else if T[m] > x then r ← m-1
        else l ← m+1
return 0

思想：

• 通过$x$与中位数的比较，将原问题归结为规模减半的子问题，如果$x$小于中位数，则子问题由小于$x$的数构成，否则子问题由大于$x$的数构成。

• 对子问题进行二分检索。

• 当子问题规模为1时，直接比较x与T[m]，若相等则返回m，否则返回0。

复杂度分析：

二分检索问题最坏情况下的时间复杂度：

$W(n)=W(\lfloor n/2 \rfloor )+2 \\ W(1)=1 \\ \implies \\ \quad W(n)=\lfloor\log{n} \rfloor + 1$

二分归并排序

算法：Merge Sort(A, p, r)

输入：数组A[p..r]

输出：元素按照从小到大的排序数组A

伪代码：

if p < r
then q ← ⌊(p+r)/2⌋   // 对半划分
    Merge Sort (A, p, q) // 子问题1
    Merge Sort (A, q+1, r) // 子问题2
    Merge (A, p, q, r) // 综合解

设计思想：

• 将原问题化为分规模为n/2的2个子问题；

• 继续划分，将原问题归结为规模为n/4的4个子问题，继续…，当子问题规模为1时，划分结束。

• 从规模1到n/2，陆续归并排好序的两个子数组。每归并一次，数组规模扩大一倍，直到原始数组的规模。

时间复杂度的分析：

假设n为2的幂，二分归并排序最坏的情况下时间复杂度：

$W(n)=2W(n/2)+n-1 \\ W(1)=0 \\ \implies \\ \quad W(n) = n\log{n} - n + 1$

Hanoi塔的递归算法

算法 Hanoi(A, C, n) // n个盘子从A到C

if n = 1 then move(A, C) // 1个盘子从A到C
else Hanoi(A, B, n - 1)
    move(A, C)
    Hanoi(B, C, n - 1)

设n个盘子的移动次数为T(n)

$T(n) = 2T(n-1)+1 \\ T(1) = 1 \\ T(n) = 2^n - 1$

算法设计思想

• 将原问题归结为规模为n-1的2个子问题；

• 继续归约，将原问题归结为规模为n-2的4个子问题。继续…，当子问题规模为1时，归约过程截止。

• 从规模1到n-1，陆续组合两个子问题的解。直到规模为n。

• 分析方法：递推方程。

一般性描述

分治算法 Divide-and-Conquer(P)

if |P|<=c then S(P)
divide P into P1,P2,...,Pk
for i ← 1 to k
    yi ← Divide-and-Conquer(Pi)
Return Merge(y1, y2, ..., yk)

设计要点

• 原问题可以划分或者归约为规模较小的子问题

  子问题与原问题具有相同的性质

  子问题的求解彼此独立

  划分时子问题的规模尽可能均衡

• 子问题规模足够小时可以直接求解

• 子问题的解综合可以得到原来的解

• 算法实现：递归或者迭代

分治算法时间分析