首页 > 试题广场 >

归并排序算法的时间复杂度是（）。

[单选题]
归并排序算法的时间复杂度是（）。 


  • O(logN)
  • O(N)
  • O(N^2)
  • O(NlogN)
查看答案及解析
添加回答
推荐
缓缓故人归头像 缓缓故人归
答案：D
解析：归并排序的核心思想在于，通过每次排列有序序列更容易从而减少时间复杂度。因此，归并的算法是先分段再段内排序，排好后再归并然后继续排序直到断长等于本身长度，做最后一次排序。
接下来分析时间复杂度，假如有8个元素，那么第一次就会分为4段(8/2)，每段2个元素段内排序。然后两两归并，一共2段(8/4)，每段4个元素段内排序。最后两两归并，只有1段(8/4)，段内8个元素段内排序。因此，一共进行了(8/2)，(8/4)，(8/8)共3次分段。故 N 个元素要进行 log2N 次分段。段内排序是怎样进行的呢，是重新开辟空间，将段内元素有序放到新的空间（具体细节可以去看实现理解），因此，段内排序的时间复杂度就是 O(N)。由于是在都是在有序的基础上合并再排序，最好最坏的复杂度都将是一样的。
综上，归并排序最好最坏以及平均时间复杂度就是 O(Nlog2N)
编辑于 2019-12-17 14:22:26 回复(0)
Jino.头像 Jino.
选D。
常见排序算法复杂度如下图：

编辑于 2019-12-16 14:29:26 回复(4)
虔诚的🐷头像 虔诚的🐷

归并排序左右分别排好序，然后两部分外排，采用递归当时接着拆分，递归时间复杂度估计采用master公式，该流程公式为：

T(N)＝T(N/2）+T(N/2）+O(N)

a＝2，b＝2，d＝1，照公式求得为O(NlogN)

编辑于 2019-12-16 16:21:24 回复(0)
白驹之过隙头像 白驹之过隙
选D。
  • 归并算法采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
  • 其实现方式：先把待排序区间以中点二分； 接着把左边子区间排序； 再把右边子区间排序； 最后把左区间和右区间用一次归并操作合并成有序的区间。
发表于 2019-12-16 17:45:18 回复(0)
哈~喽头像 哈~喽
D
发表于 2019-12-17 09:05:02 回复(0)
旧城里有光头像 旧城里有光
d
发表于 2019-12-16 18:13:16 回复(0)
世界的终结头像 世界的终结
d
发表于 2017-02-22 02:46:27 回复(0)
提交观点

问题信息

复杂度 排序
上传者：城市里的养猫者
难度：
7条回答 3866浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号