归并排序的时间复杂度分析

归并排序涉及递归到了递归,通过这篇博客,可以看下如何分析递归的时间复杂度。

一个问题 a 可以分解成多个子问题 b,c,可以得到下面的公式

T(a) = T(b) + T(c) + K

假设对 n 个元素进行归并排序,需要的时间为 T(n)。分解成两个子数组后,那么每个子数组的排序需要的时间就为 T(n/2)。而合并两个有序子数组的时间复杂度为 O(n)。所以归并排序的时间复杂度计算公式为

T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1

因为 T(n/2) = 2 * T(n/4) + n/2,所以

T(n) = 2 * (2 * T(n/4) + n/2) + n
     = 2^2 * T(n / 2^2) + 2 * n

根据 T(n/4) = 2 * T(n/8) + n/4,可以得到

T(n) = 2^3 * T(n / 2^3) + 3 * n

以此类推,可以知道

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

T(n / 2^k)=T(1),也就是 n / 2^k = 1,则 k = logn (这里 log 的 base 是 2)。把 k 的值代入上面的公式,可以得到 T(n)=Cn+nlogn,用大 O 标记就是 O(nlogn)

2018.12.04
Powered by Cubi,  Hosted by Coding Pages