归并排序算法为什么每个节点时间复杂度O(n)?

来源：2-5 递归算法的复杂度分析

时间流逝unity

2018-11-11

而二分搜索算法递归树中每个节点的时间复杂度是O(1)?

写回答

1回答

liuyubobobo

2018-11-12

已采纳

因为归并排序在每个节点，是对一个范围内的数组进行归并，我们对一个范围内的元素做操作，显然不是O(1)的。

归并排序的详细复杂度分析，可以参考这里：http://coding.imooc.com/learn/questiondetail/53158.html

而二分搜索，每次只是找到一个数值，判断它的大小，这个操作是O(1)的：）

时间流逝unity

非常感谢！

2018-11-12

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 2

回答 1

回答 1

回答 1

回答 1