关于视频中归并排序的递归时间复杂度分析的一点疑问

Question

在递归中进行多次递归调用的部分，老师举了归并排序的例子，但按照前一个例子的分析思路，若传入待排序序列的长度n，则递归树的深度为logn，每次递归又进行了2次递归，那么递归树的节点数也就是递归调用的总次数是2^(logn+1)-1，为什么时间复杂度还是O(nlogn)呢？

这部分不太能理解，希望老师能给予指点。

Answer 1

liuyubobobo 2018-04-18 13:23:48

虽然每次递归又进行了两次递归，但是两次递归处理的节点数都是原来这个递归节点数的1/2。你计算的节点数没有错，但是递归树每个节点上的运算时间是不等的。可以按照极端情况去看。在顶层那个节点，要merge处理整个数组的数据，节点内的复杂度是O(n)的；但是在递归树的叶子节点，根本不需要merge操作，复杂度是O(1)的。

可以再回顾一下我在视频中画的递归树示意图：

归并排序第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)的：）

• 提问者 很厉害的jq #1

  非常感谢老师又快又详细的解答，明白了！

• hellocp7 #2

  老师你好，如果这样的话，那另外那个O(2^n)复杂度的算法，递归深度是n，每一层的节点也是n，这样的话复杂度是否就是O(n^2)了

• liuyubobobo 回复 hellocp7 #3

  你说的是哪个算法？

Answer 2

慕圣7002650 2024-02-23 09:55:36

这里我一开始也不明白，后来想明白了。

计算递归调用的复杂度有两点，分别是递归调用的次数与单次递归的时间。

递归调用的次数就是节点数。单次递归的时间在不同的算法里面是不同的。

第一个例子单次递归的时间可以看成常数，第二个例子单次递归的时间是mergesort。

如果了解mergesort，可以知道这是一个O(n)级别的算法。注意这里的n不是整个归并排序的数据量，而是传入mergesort里面的数据量。

bobo老师在这里把每一层看成一个整体，是因为每一层的计算量（都是n）是一样的。

bobo老师在第一个例子里面把一个节点看成一个整体，是因为每一个节点的计算量（都是1）是一样的

故而两种递归的思路不同，但可总结如下：

找递归调用的次数与单次递归的时间。（但不是所有的算法都能够有一个巧妙的视角来找出某一层或者某一个递归调用时间相同）

具体可以列出数学公式计算，也就是老师后面说的主定理。

• liuyubobobo #1

  大赞，感谢你的分享：）