组合算法

『组合数学』5 组合算法

分治策略

• 最好情况：令$N = 2^n$情形

• $T_n = 2T_{n-1}+2^{n-1}$

  $G(x) = \sum_{i=0}^nT_ix^i = \frac{1}{(1-2x)^2} \\ \qquad = \sum_{i=0}^n n2^{n-1}x^n \Rightarrow T_n = n2^{n-1} = \frac 12 N\log_2^N$

• 最坏情况的复杂性分析

• $C_n = 2C_{n-1} +2^n-1$

  则其母函数为

  $G(x) = \sum_{i=1}^nC_ix^i \\ \qquad =\frac{1}{(1-2x)^2} + \frac{2x}{(1-2x)^2}+ \frac 1 {1-x} -\frac 1{1-2x}$

  展开分解得：

  取$x^n$的系数$= C_n = (n+n-1-1)2^{n-1} \\= (n-1)2^n -1 = N\log_2^N -N+1 = O(nlogn)$

快速排序

• 最好与最坏情况类似，

• 平均情况

  以等概率分布$T_n = n-1+\frac 1n\sum\limits_{k=1}^n(T_k+T_{n-k}) = \frac 2n\sum\limits_{k=0}^{n-1}T_k+n-1$

  于是有

  $T_{n+1} = n+\frac 2{n+1}\sum\limits_{k=0}^nT_k \\\Rightarrow (n+1)T_{n+1}-nT_n = n +2T_n\\\Rightarrow\frac {T_{n+1}}{n+2} - {\frac{T_n}{n+1}} = \frac{2n}{(n+1)(n+2）} \\ \Rightarrow Z_{n+1}-Z_n = \frac{4}{n+2}-\frac 2{n+1} \\ \Rightarrow T_n =(n+1)Z_n = (n+1)(2\sum\limits_{k=2}^{n-1}\frac 1{k+1}+\frac 4{n+1}-2)\\<(n+1)(2\ln n -2(n+1)ln2 +2)\in O(n\log n)$

  • [ ] 若数据以泊松分布而非等概率求其平均情况