分治策略-基础.md

基础思想

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

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

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

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

注意:

  1. 子问题和原始问题性质完全一样;(递归基础)

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

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

问题

二分搜索

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

输入:数组TT,下标从llrr;数xx

输出:jj // 若xxTT中,jj为下标;否则为00

伪代码:

1
2
3
4
5
6
7
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

思想:

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

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

  • 当子问题规模为1时,直接比较xT[m],若相等则返回m,否则返回0

复杂度分析:

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

W(n)=W(n/2)+2W(1)=1W(n)=logn+1W(n)=W(\lfloor n/2 \rfloor )+2 \newline W(1)=1 \newline 解出 \quad W(n)=\lfloor\log{n} \rfloor + 1

二分归并排序

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

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

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

伪代码:

1
2
3
4
5
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时,划分结束。

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

时间复杂度的分析:

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

W(n)=2W(n/2)+n1W(1)=0W(n)=nlognn+1W(n)=2W(n/2)+n-1 \\ W(1)=0 \\ 解出 \quad W(n) = n\log{n} - n + 1

Hanoi塔的递归算法

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

1
2
3
4
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(n1)+1T(1)=1T(n)=2n1T(n) = 2T(n-1)+1 \\ T(1) = 1 T(n) = 2^n - 1

算法设计思想

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

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

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

  • 分析方法:递推方程。

一般性描述

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

1
2
3
4
5
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)

设计要点

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

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

    子问题的求解彼此独立

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

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

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

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

分治算法时间分析

作者

Hu

发布于

2021-09-07

更新于

2021-08-25

许可协议

评论