分治策略-算法设计思想.md

算法设计思想

  • 将原问题归结为规模为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)

设计要点

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

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

    子问题的求解彼此独立

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

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

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

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

分治算法时间分析

时间复杂度函数的递推方程:

W(n)=W(P1)+W(P1)+...+W(P1)+f(n)W(c)=CW(n)=W(|P_1|)+W(|P_1|)+...+W(|P_1|)+f(n) \\ W(c)=C

  • P1,P2,...,PkP_1, P_2, ..., P_k为划分后产生的子问题

  • f(n)f(n)为划分子问题以及将子问题的解综合得到原问题解的总工作量

  • 规模为cc的最小子问题的工作量为CC

两种常见的递推方程

f(n)=i=1kaif(ni)+g(n)f(n)=af(nb)+d(n)f(n)=\sum_{i=1}^{k}a_if(n-i)+g(n) \newline f(n)=af(\frac{n}{b})+d(n)

  • Hanoi塔,W(n)=2W(n1)+1W(n)=2W(n-1)+1

  • 二分检索,W(n)=W(n/2)+1W(n)=W(n/2)+1

  • 归并排序,W(n)=2W(n/2)+n1W(n)=2W(n/2)+n-1

对于方程1f(n)=i=1kaif(ni)+g(n)f(n)=\sum_{i=1}^{k}a_if(n-i)+g(n)求解方法有迭代法、递归树;对于方程2f(n)=af(nb)+d(n)f(n)=af(\frac{n}{b})+d(n)有迭代法、换元法、递归树、主定理。

方程2

方程 T(n)=aT(n/b)+d(n)T(n)=aT(n/b)+d(n)

d(n)d(n)为常数时,

T(n)={O(nlogba)a1O(logn)a=1T(n) = \begin{cases} \Omicron(n^{\log_ba}) &{a \neq 1} \\ \Omicron(\log {n}) &{a = 1} \end{cases}

d(n)=cnd(n)=cn时,

T(n)={O(n)a<bO(nlogn)a=bO(nlogba)a>bT(n) = \begin{cases} \Omicron(n) &{a < b} \\ \Omicron(n \log {n}) &{a = b} \\ \Omicron(n^{\log_ba}) &{a > b} \end{cases}

分治策略-算法设计思想.md

https://hoooo.org/2021/09/07/divide_conquer_2/

作者

Hu

发布于

2021-09-07

更新于

2021-08-25

许可协议

评论