算法 - 关于归并排序时间复杂度 T（n） =2T（n/2）+O（n）

问题描述

问 题

T（n）=2T（n/2）+O（n），n=2^k。
想知道为什么最终答案为O（nlgn）

解决方案

Master大法好。这题自己推导也不难。把递推公式重复代入三次并化简：

$$\array{\text{1}:&T(n)<2\ T(\frac{n}{2})+ c\ n\\\ \text{2:}&\ \ T(n)<4\ T(\frac{n}{4})+ 2\ c\ n\\\ \text{3:}&\ \ T(n)<8\ T(\frac{n}{8})+ 3\ c\ n}$$

可以看出规律了，而且很容易用归纳法证明。于是代入$k$次时就有（$n=2^k$）：

$$\array{\qquad\text{k}:&T(n)<2^k\ T(\frac{n}{2^k})+ k\ c\ n\\&\quad\ \qquad=n\ T(1) + c\ n\ \log_2{n}\\&=\Theta(n\log{n})}$$

这篇关于算法 - 关于归并排序时间复杂度 T（n） =2T（n/2）+O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！