首页 > 试题广场 >

在下列排序方法中，空间复杂性为O(log2n)的方法为多少？

[单选题]
在下列排序方法中，空间复杂性为O(log2n)的方法为多少？ 
  • 直接选择排序
  • 归并排序
  • 堆排序
  • 快速排序
  • 冒泡排序
添加回答
算法妙妙屋头像 算法妙妙屋
选D，A,E都是O(1)不用说，B只要带上O（n）的空间把地址传来传去就只有O（n）的消耗，堆排序是可以就地排序的，每次弹出元素后，堆容量减一，然后直接将堆顶元素放在减一时空出来的那个位置就好了，D其实是最不好说的，D的空间复杂度相当于递归的深度，递归的深度在平均意义上是O(logn)，最坏情况是O（n），如果每次都是二分的话，logn就结束了递归，如果每次都不凑巧，都只能将规模减少1那就是O（n）的空间复杂度了
编辑于 2015-09-05 13:09:00 回复(4)
更多回答
IreanLau头像 IreanLau
快排  O(log2n)~O(n)  
发表于 2015-09-19 13:58:59 回复(0)
Aesthetic92头像 Aesthetic92
A: O(1)
B: O(n)
C: O(1)
D: O(log2n)~O(n)  递归
E: O(1)

选D
发表于 2014-12-29 12:28:08 回复(0)
诸葛狼头像 诸葛狼
D
发表于 2015-09-05 22:13:55 回复(0)
舍我其谁头像 舍我其谁
选D
发表于 2015-09-05 21:56:02 回复(0)
牛客854445号头像 牛客854445号
A：O(1)
B：O(n)
C：O(1)
D：O(log2n)
E：O(1)
发表于 2015-09-05 18:12:28 回复(0)
触发头像 触发 
这个图片相当不错

发表于 2015-09-05 16:38:02 回复(0)
彭泽头像 彭泽
发表于 2015-09-05 14:32:50 回复(0)
codermanFans头像 codermanFans
选D，快速排序中会出现递归调用，所以每次递归的情况下都会保存交换的数据，并且交换两个数的位置交换log2N次空间复杂度应该就是log2N
发表于 2015-09-05 09:16:05 回复(0)
提交观点

问题信息

网易 排序
上传者：whj
难度：
9条回答 9997浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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