目录
  1. 1. 主定理 Master Theorem
    1. 1.1. 内容
    2. 1.2. 实际应用
    3. 1.3. 举例
      1. 1.3.1. 二分查找 Binary Search
      2. 1.3.2. 快速排序 Quick Sort
      3. 1.3.3. 归并排序 Merge Sort
      4. 1.3.4. 基数排序 Radix Sort
      5. 1.3.5. 二叉树的遍历 Traversing Binary Tree
主定理 Master Theorem

主定理 Master Theorem

对于采用分治策略的算法, 其递归方程一般可用主定理口算求解

内容

假设有递推关系式 T(n)=aT(nb)+Θ(n), a1,b>1T(n) = aT(\dfrac{n}{b}) + \Theta(n), \space a \ge 1, b > 1 其中,

  • nn 为问题规模
  • aa 为递归子问题的数量
  • nb\dfrac{n}{b} 为每个子问题的规模 假设每个子问题的规模基本一样
  • f(n)f(n) 为递归以外进行的计算

则该算法的渐进时间复杂度 O\Omicron 可分为以下三种情形讨论

  • 情形1:

    如果  ϵ>0 (ϵ)\exists \space \epsilon > 0 \space (\epsilon 为一常数), 有 f(n)=O(nlogbaϵ) ()f(n) = \Omicron (n^{\log_{b}{a} - \epsilon}) \space (多项式地小于)

    T(n)=Θ(nlogba)T(n) = \Theta (n^{\log_{b}{a}})

  • 情形2:

    如果 k0, (k)\exists \space k \ge 0, \space (k为一常数), 有 f(n)=Θ(nlogbalogkn)f(n) = \Theta (n^{\log_{b}{a}} \log^{k}n)

    T(n)=Θ(nlogbalogk+1n)T(n) = \Theta (n^{\log_{b}{a}} \log^{k + 1}n)

  • 情形3:

    如果  ϵ>0 (ϵ)\exists \space \epsilon > 0 \space (\epsilon 为一常数), 有 f(n)=Ω(nlogba+ϵ) ()f(n) = \Omega(n^{\log_{b}{a} + \epsilon}) \space (多项式地大于)

    同时  c<1 (c)\exists \space c < 1 \space (c为一常数) 以及充分大的 nn 满足 af(nb)cf(n)af(\dfrac{n}{b}) \le cf(n)

    T(n)=Θ(f(n))T(n) = \Theta (f(n))

实际应用

在实际使用中我们并不需要记得那么复杂…

大概就记住下面一串?

 T(n)=aT(nb)+c(nd) , a1 ,b>1 T(n)={Θ(ndlogn) ,a=bdΘ(nd) ,a<bdΘ(nlogba) ,a>bd设递归方程为 \space T(n) = aT(\dfrac{n}{b}) + c(n^{d}) \space , 其中 \space a \ge 1 \space, b > 1 \\ 则所求问题的复杂度 \space T(n) = \begin{cases} \Theta (n^{d}\log{n}) \space , a = b ^ d \\ \\ \Theta (n^d) \space , a < b ^ d \\ \\ \Theta (n^{\log_{b}{a}}) \space , a > b ^ d \end{cases}

举例

每次问题规模减半, 则 a=1 ,b=2a = 1 \space , b = 2

每次额外的计算为0, 则 d=0d = 0

所以可得递推关系式 T(n)=T(n2)+c(1)T(n) = T(\dfrac{n}{2}) + c(1)

上式满足 a=bda = b ^ d 即情形1

所以复杂度为 Θ(n0logn)=Θ(logn)\Theta (n^{0} \log{n}) = \Theta (\log{n})

快速排序 Quick Sort

每次问题规模减半, 问题划分成两部分, 则 a=2,b=2a = 2, b = 2

每次额外需要进行一次合并, 则 d=1d = 1

所以可得递推关系式 T(n)=2T(n2)+c(n1)T(n) = 2T(\dfrac{n}{2}) + c(n^1)

上式满足 a=bda = b^d 即情形1

所以复杂度为 Θ(n1logn)=Θ(nlogn)\Theta(n^1\log{n}) = \Theta(n\log{n})

归并排序 Merge Sort

每次问题规模减半, 问题划分成两部分, 则 a=2,b=2a = 2, b = 2

每次额外需要进行一次合并, 则 d=1d = 1

所以可得递推关系式 T(n)=2T(n2)+c(n1)T(n) = 2T(\dfrac{n}{2}) + c(n^1)

上式满足 a=bda = b^d 即情形1

所以复杂度为 Θ(n1logn)=Θ(nlogn)\Theta(n^1\log{n}) = \Theta(n\log{n})

基数排序 Radix Sort

假设所取的基数为basebase

每次问题规模变为1base\dfrac{1}{base},但子问题规模变为 basebase 倍, 则 a=base ,b=basea = base \space, b = base

每次需要分配一次桶为O(n)\Omicron(n), 则d=1d = 1

所以可得递推关系式 T(n)=baseT(nbase)+c(n1)T(n) = base * T(\dfrac{n}{base}) + c(n^1)

上式满足 a=bda = b^d 即情形1

所以复杂度为 Θ(n1logn)=Θ(nlogn)Θ(wn)\Theta(n^1\log{n}) = \Theta(n\log{n}) \simeq \Theta(w * n)

Radix sort complexity is O(wn)\Omicron(wn) for n keys which are integers of word size w.

二叉树的遍历 Traversing Binary Tree

每次问题规模减半, 问题划分成两部分, 则 a=2,b=2a = 2, b = 2

每次额外的计算为0, 则 d=0d = 0

所以可得递推关系式 T(n)=2T(n2)+c(1)T(n) = 2T(\dfrac{n}{2}) + c(1)

上式满足a>bda > b^d 即情形3

所以复杂度为Θ(nlog22)=Θ(n)\Theta(n^{\log_{2}2}) = \Theta(n)

文章作者: Twiliness
文章链接: https://twiliness.xyz/2019/10/04/Master-Theorem/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Twilight Spring