首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
admin
2014-12-25
45
问题
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
选项
答案
O(nlog
2
n) O(n
2
)
解析
快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需log
2
n趟划分即可。每趟划分所需时间复杂度为O(n)，最好情况下的时间复杂度是O(nlog
2
n)。
最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n一1趟划分。每趟划分的时间复杂度为O(n)，因此，最坏情况下的时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/2iVx777K
本试题收录于：
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
已知单位负反馈控制系统的开环传递函数为G(s)=，当输入信号为r(t)=1时，系统的稳态误差ess为________。
一系统在扰动作用下的误差函数为EN(s)=，则系统由扰动引起的稳态误差essN等于【】
为了便于书写和阅读，IPv4地址通常采用_______个十进制数来表示。
下面给出的是一份不完整的HTML文档，请根据HTML的基本语法规则补充填写①、②、③、④处所缺少的标记，并简要说明该文档中的标记＜IMGSRC=’’D：／picture．jPg’’＞的作用。＜HTML＞＜HEAD＞
地址256．96．209．5是一个________(合法／非法)的IP地址。
面向连接服务包括建立连接、传输数据和________三个阶段。
在以太网的MAC层，数据是以【】的形式存在的。
当客户端要从服务器中读取文档时，通过单击网页上的链接或者在浏览器的地址栏中输入网址来浏览网页，使用的都是【】方法。
在常用的网络性能测评指标中，【】通常用平均无故障时间(MTDF)来衡量。
在SQLserver2000中，不是系统数据库的是()
随机试题
Itwasvery______ofyounottoplaythepianowhileIwashavingasleep.
下列哪项不属于问诊中个人生活史的内容
下列哪一种介质或细胞因子不参与I型超敏反应
肾病综合征不具有下列哪项特点()
关于经理层人员，下列说法错误的是()。
根据《物业管理师制度暂行规定》，物业管理师未经授权，不得履行的职责是()
中国营养协会建议孕妇在孕早中晚期膳食蛋白质RNI增加值分别为5、15、20g／日。()
马家窑文化彩陶的纹饰有人物纹、动物纹、螺旋纹和波浪纹。()
A、angerB、anxietyC、fearD、hatredB
A、85.B、100.C、40.D、125.B
最新回复
(
0
)
