第三章递归分治

归并排序

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)

递归式

\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. }

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

\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} }

\displaystyle{ T \left( n \right) \in \Theta \left( n \log n \right) }

举例

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

$\displaystyle{ k = \log n }$

\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} }

递归式

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

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

主定理

\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

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

$\displaystyle{ f \left( n \right) = \Theta \left( n ^{ c } \log ^{ k } n \right) , c = 1 , k = 0 }$

$\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) }$

主定理的另一种形式

\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最优性原理：

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

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

第三章 递归分治

归并排序

第三章递归分治