A = [3. 4. 1. 6. 7. 2. 5 .9]
目标: sort ( A )
方案：拆分子问题
a1 = [3, 4, 1, 6]
a2 = [7, 2, 5, 9]
a11 = [3, 4]
a12 = [1, 6]
…
a111 = [3]
a112 = [4]
3 < 4 —- 3 放在4左边 以此类推
复杂度
$T ( n ) = T ( n / 2 ) + T ( n / 2 ) + n$
$T ( n ) = 2 T ( n / 2 ) + n$
… Master Theorem 假设有递推关系 $T(n) = a ; T!\left(\frac{n}{b}\right) + f(n)，$其中 $a \geq 1 \mbox{, } b > 1$
… —- 有 $\left( n^{\log_b (a)} \right) > f(n)$ —- $\Theta\left( n^{\log_b a} \right)$
… —- 有 $\Theta\left( n^{\log_b a} \log^{\epsilon} n \right) == f(n)$ —- $\Theta\left( n^{\log_b a} \log^{\epsilon+1} n \right)$
… —- 有 $\Omega\left( n^{\log_b (a) + \epsilon} \right) < f(n)$ —- $\Theta \left(f \left(n \right) \right)$
$T ( n ) = T ( n · log n )$
疑问
为什么是拆分为2个子问题，而不是多个
当最后归并的时候判断多次的复杂度要比单次的复杂度高
