Skip to content
Notes
GitHub

第三章 递归分治

归并排序

def merge_sort(arr, p, r):
  if p < r:
    q = (p + r) // 2
    merge_sort(arr, p, q)
    merge_sort(arr, q + 1, r)
    merge(arr, p, q, r)
def merge_sort(arr, p, r):
  if p < r:
    q = (p + r) // 2
    merge_sort(arr, p, q)
    merge_sort(arr, q + 1, r)
    merge(arr, p, q, r)

递归式

T(n)={1ifn=12T(n/2)+nifn>1\displaystyle{ T \left( n \right) = \left\lbrace \begin{array}{ll} 1 & \text{if}\quad n = 1 \\ 2 T \left( n {/} 2 \right) + n & \text{if}\quad n > 1 \end{array} \right. }

如果 n=2k\displaystyle{ n = 2 ^{ k } }

T(2k)=2T(2k−1)+2k=2(2T(2k−2)+2k−1)+2k=22T(2k−2)+2k+2k=…=2kT(2k−k)+2k+…+2k=2k+k2k\displaystyle{ \begin{aligned}T \left( 2 ^{ k } \right) & = 2 T \left( 2 ^{ k - 1 } \right) + 2 ^{ k } \\ & = 2 \left( 2 T \left( 2 ^{ k - 2 } \right) + 2 ^{ k - 1 } \right) + 2 ^{ k } \\ & = 2 ^{ 2 } T \left( 2 ^{ k - 2 } \right) + 2 ^{ k } + 2 ^{ k } \\ & = \ldots \\ & = 2 ^{ k } T \left( 2 ^{ k - k } \right) + 2 ^{ k } + \ldots + 2 ^{ k } \\ & = 2 ^{ k } + k 2 ^{ k }\end{aligned} } T(n)∈Θ(nlog⁡n)\displaystyle{ T \left( n \right) \in \Theta \left( n \log n \right) }

举例

T(n)=2T(n2)+n2\displaystyle{ T \left( n \right) = 2 T \left( \frac{ n }{ 2 } \right) + n ^{ 2 } }

k=log⁡n\displaystyle{ k = \log n }

∑i=0k−112in2+2k=n2(1−0.5k1−0.5)+n=2n2+n∈Θ(n2)\displaystyle{ \begin{aligned}\sum _{ i = 0 } ^{ k - 1 } \frac{ 1 }{ 2 ^{ i } } n ^{ 2 } + 2 ^{ k } & = n ^{ 2 } \left( \frac{ 1 - 0.5 ^{ k } }{ 1 - 0.5 } \right) + n \\ & = 2 n ^{ 2 } + n \in \Theta \left( n ^{ 2 } \right)\end{aligned} }

递归式

T(n)=aT(n/b)+f(n)\displaystyle{ T \left( n \right) = a T \left( n {/} b \right) + f \left( n \right) }

其中，a⩾1,b>1\displaystyle{ a \geqslant 1 , b > 1 } 是两个常数，f(n)\displaystyle{ f \left( n \right) } 是一个渐近非负函数

主定理

T(n)={Θ(nlog⁡ba)iff(n)∈O(nlog⁡ba−ε), ε>0Θ(nlog⁡balg⁡k+1n)iff(n)∈Θ(nlog⁡balg⁡kn), k⩾0Θ(f(n))iff(n)∈Ω(nlog⁡ba+ε), ε>0 and af(n/b)⩽cf(n) for some c<1 andall sufficiently large n\displaystyle{ T \left( n \right) = \left\lbrace \begin{array}{ll} \Theta \left( n ^{ \log _{ b } a } \right) & \text{if}\quad f \left( n \right) \in O \left( n ^{ \log _{ b } a - \varepsilon } \right) \text{, } \varepsilon > 0 \\ \Theta \left( n ^{ \log _{ b } a } \operatorname{ lg } ^{ k + 1 } n \right) & \text{if}\quad f \left( n \right) \in \Theta \left( n ^{ \log _{ b } a } \operatorname{ lg } ^{ k } n \right) \text{, } k \geqslant 0 \\ \Theta \left( f \left( n \right) \right) & \text{if}\quad f \left( n \right) \in \Omega \left( n ^{ \log _{ b } a + \varepsilon } \right) \text{, } \varepsilon > 0 \text{ and } \\ & a f \left( n {/} b \right) \leqslant c f \left( n \right) \text{ for some } c < 1 \text{ and} \\ & \text{all sufficiently large } n \end{array} \right. }
Example

T(n)=2T(n/2)+10n\displaystyle{ T \left( n \right) = 2 T \left( n {/} 2 \right) + 10 n }

f(n)=Θ(nclog⁡kn),c=1,k=0\displaystyle{ f \left( n \right) = \Theta \left( n ^{ c } \log ^{ k } n \right) , c = 1 , k = 0 }

T(n)=Θ(nlog⁡balog⁡k+1n)=Θ(n1log⁡1n)=Θ(nlog⁡n)\displaystyle{ T \left( n \right) = \Theta \left( n ^{ \log _{ b } a } \log ^{ k + 1 } n \right) = \Theta \left( n ^{ 1 } \log ^{ 1 } n \right) = \Theta \left( n \log n \right) }

主定理的另一种形式

T(n)={Θ(nlog⁡ba)iff(n)nlog⁡ba∈O(n−ε), ε>0Θ(nlog⁡balog⁡k+1n)iff(n)nlog⁡ba∈O(log⁡kn), k⩾0Θ(f(n))iff(n)nlog⁡ba∈Ω(nε), ε>0, af(n/b)⩽cf(n) for some c<1 andall sufficiently large n\displaystyle{ T \left( n \right) = \left\lbrace \begin{array}{ll} \Theta \left( n ^{ \log _{ b } a } \right) & \text{if}\quad \frac{ f \left( n \right) }{ n ^{ \log _{ b } a } } \in O \left( n ^{ {-\varepsilon } } \right) \text{, } \varepsilon > 0 \\ \Theta \left( n ^{ \log _{ b } a } \log ^{ k + 1 } n \right) & \text{if}\quad \frac{ f \left( n \right) }{ n ^{ \log _{ b } a } } \in O \left( \log ^{ k } n \right) \text{, } k \geqslant 0 \\ \Theta \left( f \left( n \right) \right) & \text{if}\quad \frac{ f \left( n \right) }{ n ^{ \log _{ b } a } } \in \Omega \left( n ^{ \varepsilon } \right) \text{, } \varepsilon > 0 \text{, } \\ & a f \left( n {/} b \right) \leqslant c f \left( n \right) \text{ for some } c < 1 \text{ and} \\ & \text{all sufficiently large } n \end{array} \right. }

Bellman最优性原理：

  • 求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。
  • 注：对具有最优性原理性质的问题而言，如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。

动态规划的思想实质是分治思想和解决冗余，分支中有共同的部分被重复计算了很多次，动态规划将这部分结果保存，避免重复计算