首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
admin
2014-12-25
49
问题
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
选项
答案
O(nlog
2
n) O(n
2
)
解析
快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需log
2
n趟划分即可。每趟划分所需时间复杂度为O(n)，最好情况下的时间复杂度是O(nlog
2
n)。
最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n一1趟划分。每趟划分的时间复杂度为O(n)，因此，最坏情况下的时间复杂度为O(n
2
)。
转载请注明原文地址:https://www.kaotiyun.com/show/2iVx777K
本试题收录于：
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
单位反馈系统的开环传递函数为G(s)=，则在单位斜坡输入下的稳态误差为【】
简述典型二阶系统(当0＜ζ＜1，ζ=0，ζ≥1时)在单位阶跃输入信号作用下的输出响应特性。
在时域中用线性常微分方程描述系统的动态特性；在复数域或频域中，用________来描述系统的动态特性。
若化简后的IPv6地址为BC62：：63FA：0000：0000：0000，则化简前的IPv6地址为_______。
NetWare网络操作系统大部分安装于服务器上，这部分称为_____，负责管理网络。
______是由Cisco公司专门为小型和中型网络开发的一套基于PC的集成式网络配置和诊断工具。
______是指将数据备份到与本地计算机相隔离的存储介质中，常用的有移动硬盘、U盘、光盘和网络空间等。
操作系统的【】是指在多道程序环境下，由于资源的竞争或共享，程序的执行会走走停停，因此多个程序的执行顺序及所需的执行时间将变得不可预知。
下列软件中，不是基于P2P模式的是【】
网络图的结点符号是在圆圈的上半方标以________；下半部分的左侧标以该结点(事项)的最早开始时间值，右侧标以该结点(事项)的最迟完成时间值。
随机试题
BSP方法()地进行系统规划。
对肺结核病描述中错误的是（）
此病例适宜的手术时机是此例首选的搭桥材料是
功能性电刺激应用范围不包括
如借款人未经银行批准擅自改变款项用途，银行可以不予支付剩余贷款。()
个人住房贷款期限在一年以下(含一年)的，采用的还款方式为()。
在政府采购合同履行中，采购人需追加与合同标的相同的货物、工程或者服务的，在不改变合同其他条款的前提下，可以与供应商协商签订补充合同，但所有补充合同的采购金额不得超过原合同采购金额的20%。()
法国作家雨果说：“最大的决心会产生最高的智慧。”下列与这句话蕴含相似哲理的是：
简述交易吞吐量和交易响应时间的概念。在并发用户数为50时，如果交易吞吐量和交易响应时间都不满足需求，简述数据库端造成此缺陷的主要原因，有效的解决方案是什么?
Onanaverageofsixtimesaday,adoctorinHollandpractices"active"euthanasia:intentionallyadministeringalethaldrugt
最新回复
(
0
)
