算法笔记 7 归并排序和快速排序（下）

微信公众号：珷玞的日常

归并排序时间复杂度分析

归并排序是递归完成的，对于递归时间复杂度，也可以写成一个递推公式：

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

其中 T(a) T(b) T(c) 分别代表总任务、两个分任务求解所需的时间，k 是将两个分问题进行合并所需的时间。

再回到归并排序，归并排序每次将序列分为两个大小相同的子数组，即 T(b) = T(c) = T(a/2)；对于合并过程，也就是 merge 函数，时间复杂度为 O(n)。所以总的时间复杂度公式如下：

T(1) = C

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

然后推导 T(n)

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

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

    = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n

    = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n

    ......

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

    ......

得到 T(n) = 2^k * T(n/2^k) + kn，当 T(n/2^k)=T(1) 时，也就是分解到最小单元时，k = log2(n)，带入到 T(n)，得 T(n) = cn + nlog2(n)，时间复杂度也就是 O(nlogn)

因为 loga(b) = logc(b)/logc(a)，其中 logc(a) 为常数，在时间复杂度里常数可以省略，所以用什么为底也就不重要了。

快速排序和归并排序的一点区别

快速排序和归并排序都是分治思想，两者相似度很高，但它们也是有不同之处的。

从图中可以看到，归并排序是由下到上进行，先处理子问题，然后合并。快速排序则不然，它的处理方式是自上而下的，先分区，然后在处理子问题。也正是因为快速排序的这种特性，使得它可以在原地执行，而归并排序的合并函数无法进行原地执行。