计算科学 - 如何证明归并排序的时间复杂度 - 吾爱随笔录

如何证明归并排序的时间复杂度

计算科学算法复杂

2021-11-27 21:52:51

我被要求证明归并排序的时间复杂度是 $O(log_2n)$ 但我找不到继续我的方法的方法。有什么帮助吗？

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

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

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

$...$

$T(n)= 2^kT(\frac{n}{2^k})+(2^k-1)n$

最后 $\frac{n}{2^k}=1$ 和 $\therefore n=2^k$

我不知道如何从这里继续证明它是 $O(log_2n)$

2个回答

您可以自己做代数，也可以应用主定理http://en.wikipedia.org/wiki/Master_theorem

它实际上是 n(log2n)，而不是 log2n（比较排序都受限于 nlogn 性能）。

看起来你错过了除以二。从顶部开始（抱歉不知道LaTeX），

T(n) =  2 T(n/2) + n

     =  2 [2 T(n/4) + n/2] + n

     =  4 T(n/4) + 2n

     = 4 [2 T(n/8) + n/4] + 2n

     = 8 T(n/8) + 3n

     = 2^k T(n/2^k) + kn

根据您对 n/2^k = 1 的观察，我们可以将每一边乘以 2^k，取对数，然后找到 log2 n = k。将它插入我们之前的位置，

T(n) = 2^(log2 n)*T(1) + (log2n)*n

     = n*T(1) + (log2n)*n

     = n + (log2n)*n

     = (log2n)*n

其它你可能感兴趣的问题

上一篇求解具有线性源项的扩散方程下一篇如何为 ODE 系统调用 Boost C++ odeint Runge-Kutta 积分器？