首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
在下列几种排序方法中,空间复杂度最高的是()
[单选题]
在下列几种排序方法中,空间复杂度最高的是()
归并排序
快速排序
插入排序
选择排序
添加笔记
邀请回答
收藏(132)
分享
纠错
8个回答
添加回答
10
推荐
已注销
正确答案选A
归并排序空间复杂度为O(n)
快速排序:
就地快排空间复杂度为O(1)
使用递归:
每一次都平分数组,即最优情况是O(logn)
退化为冒泡排序,即最差情况是O(n)
插入和选择都是O(1)
编辑于 2017-05-24 14:55:59
回复(0)
2
一切都会好起来的吧
关于快速排序的空间复杂度的问题并不是简单的nlogn
首先就地快速排序使用的空间是O(1)的,也就是个常数级;而真正消耗空间的就是递归调用了,因为每次递归就要保持一些数据;
最优的情况下空间复杂度为:O(logn) ;每一次都平分数组的情况
最差的情况下空间复杂度为:O( n ) ;退化为冒泡排序的情况
发表于 2018-06-12 21:02:09
回复(0)
3
食货
归并涉及到合并问题,需要申请临时空间存放临时结果
发表于 2016-12-20 17:37:53
回复(0)
2
美团到店招聘
空间复杂度:
归并排序:O(n)
快排:O(logn)
插入排序:O(1)
选择排序:O(1)
发表于 2017-02-19 20:00:45
回复(0)
0
fghfghggh
归并不是O(1)吗?
发表于 2018-10-07 14:10:18
回复(0)
0
侯卿
其实归并排序的空间复杂度可以优化为O(1),感兴趣的同学可以Google一下。
发表于 2018-01-26 10:44:06
回复(0)
0
巅峰斌
归并需要构造多个辅助数组,必然需要很多空间
发表于 2017-12-18 12:17:07
回复(0)
0
sunlight_run
归并涉及到合并问题,需要较多中间存储空间
发表于 2017-07-06 19:56:31
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
C++工程师
4399游戏
2017
复杂度
排序
Java工程师
销售
来自:
职能类模拟题1
上传者:
牛100
难度:
8条回答
132收藏
5954浏览
热门推荐
相关试题
下列关于 http 状态码描述正确...
网络基础
前端工程师
2017
4399游戏
评论
(12)
来自
4399公司2017秋招...
以上 JavaScript 代码,...
Javascript
前端工程师
2017
4399游戏
评论
(39)
来自
4399公司2017秋招...
执行以下 JavaScript 代...
Javascript
前端工程师
2017
4399游戏
评论
(69)
来自
4399公司2017秋招...
<p> <sp...
Java工程师
C++工程师
2017
4399游戏
销售
评论
(4)
来自
职能类模拟题1
对于小红书,创作者和粉丝之间互相不...
需求分析
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题