归并排序中递归是如何降低时间复杂度的?
你产生这个疑问的核心原因是课程的表述出现了偏差,不存在「递归实现拆分数组的复杂度低于循环实现」的情况:
- 课程里提到的
O(log n),实际上指的是归并排序递归拆分的层数,而非拆分阶段的总时间复杂度。 - 不管是递归拆分还是你给出的循环拆分实现,拆分阶段的总时间复杂度都是
O(n),二者没有量级差异。
具体解释
- 你写的循环
divide函数逻辑是直接把原数组的每个元素单独封装为长度为1的子数组,只需要遍历一次原数组,操作数就是n,复杂度确实是O(n)。 - 递归拆分的逻辑是每次把当前数组对半拆成两个子数组,直到所有子数组长度为1:
- 整个拆分过程会有
log₂n层,每层拆分操作涉及的元素总数加起来刚好是n,总操作数仍然是O(n)量级,和循环实现的复杂度是一致的。 - 课程错误地把递归调用的层数、或者单次拆分的操作数当成了总拆分复杂度,才会出现
O(log n)的错误表述。
- 整个拆分过程会有
- 归并排序的整体时间复杂度
O(n log n),主要贡献来自合并阶段:每层合并操作的总操作数是n,共log n层,所以总复杂度是n * log n。拆分阶段的O(n)复杂度和合并阶段相比占比极低,很多讲解会刻意弱化拆分的时间成本,只强调log n层的特征,很容易造成误解。
结论
递归拆分和循环拆分的时间复杂度是同量级的,不存在谁比谁更低的情况,你看到的差异只是课程表述不严谨导致的误解。
内容的提问来源于stack exchange,提问作者Amit Kumar Gupta
相关产品推荐
相关产品推荐

