归并排序的时间复杂度是如何计算得出的？

Question

根据资料，归并排序的时间复杂度是nlogn，其中的logn是进行二分的次数的这个时间，那个n指的是什么呢？还有递归归并的过程这个时间应该怎么计算并且理解呢？

Answer 1

liuyubobobo 2017-01-22 14:15:12

n是指数据规模。在nlogn中，有两个n，这两个n是一个东西——即数据规模。其中logn的部分，如你所说，是指递归树的深度，而在递归树的每一层，都要处理n个数据的“归并问题”，即merge操作。因此，我们说归并排序的时间复杂度是O(nlogn)的。这句话是指，执行归并排序所需要的时间，是和数据规模n相关的，这个相关函数，可以表达为nlogn这个级别的。

归并排序第0层只有一个递归调用，这个递归调用的merge操作要处理n个节点；

归并排序第1层有两个调用，每个调用需要merge处理n/2个节点，总共是n/2*2=n个节点；

归并排序第2层有四个调用，每个调用需要merge处理n/4个节点，总共是n/4*4=n个节点；

....

以此类推...

归并排序第k层有2^k个调用，每个调用需要merge处理n/(2^k)个节点，总共是n/(2^k)*(2^k)=n个节点；

归并排序总共递归深度为logn，在每一层的递归，总共处理的节点个数均为n个节点，所以总体时间复杂度是O(nlogn)的：）

对于时间复杂度，实际上不是这个课程的强调重点。这个课程在设计的时候主要针对本科课堂的算法部分讲解了太多理论性的内容，但是在具体实践上一般有所欠缺，所以强调通过程序的编写实践，来体验算法的实现和优化。如果你需要了解更多算法复杂度的内容，还是需要查阅相关资料。通常算法书籍都会有专门的章节讲解这个问题的。加油！