归并排序的复杂度

根据递归方程求解:

$$T(n)=2T(\frac{n}{2})+2n$$

$$T(\frac{n}{2})=2T(\frac{n}{4})+2\frac{n}{2}$$

$$T(\frac{n}{4})=2T(\frac{n}{8})+2\frac{n}{4}$$

$$T(\frac{n}{8})=2T(\frac{n}{16})+2\frac{n}{8}$$

$$...$$

$$T(2)=2T(1)+4$$

$$T(1)=1$$

上述式子共有${\log }_{2}n$项。

考虑：

1. 因为每一项都取决于前一项，将T(1)带入T(2), T(2)带入T(4)…T(n/2) 带入T(n)后，第一部分总共有${\log }_{2}n$个2相乘, 因此第一部分值为$2^{{\log }_{2}n}=n$。
2. 第二部分为：$2n+2n+2n+..+2n$，且总共有${\log }_{2}n$项, 和为$2n{\log }_{2}n$。
3. 总共的时间复杂度为: $n+2n{\log }_{2}n=O(n{\log }_{2}n)$。
4. 思考若是递推方程第二项中是一个常数，比如O(1)，那么复杂度是多少？答案是$O(n)$。若是O(n), 则变为$O(n^2)$。
5. 若第一项中f(n/2)变为f(n/3)则时间复杂度变为O(n),请思考这样变化的原因是什么呢？

堆排序、非极限情况下的快速排序和归并排序的计算方法类似，时间复杂度都是$O(n{\log }_{2}n)$.

汉诺塔(Hanoi)的递推方程为T(n) = 2T(n-1)，分治后问题规模减1，层层带入后所得的时间复杂度为$2^n-1,即O(2^n)$。