首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
admin
2014-12-25
19
问题
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
选项
答案
O(nlog
2
n) O(n
2
)
解析
快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需log
2
n趟划分即可。每趟划分所需时间复杂度为O(n)，最好情况下的时间复杂度是O(nlog
2
n)。
最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n一1趟划分。每趟划分的时间复杂度为O(n)，因此，最坏情况下的时间复杂度为O(n
2
)。
转载请注明原文地址:https://jikaoti.com/ti/8jLaFFFM
本试题收录于：
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
试分析二阶系统在不同阻尼下特征根的形式和位置分布及其对应的阶跃响应曲线的形状。
简述差分曼彻斯特码的编码规则，并给出与题26图所示差分曼彻斯特码信号波形相对应的比特串(设线路的初始电平为-E)。
新一代网络操作系统WindowsServer2008的主要特点之一是“可管理性”，试给予具体解释。
在HTML源文件中，各种标记是由符号【】括起来的。
【】是一种最简单、廉价的以太网扩展设备，常用于连接两个以太网网段，对衰减的信号进行放大，保持与原数据相同。
存储器管理的主要功能是内存的分配和回收、______，以及内存的扩充。
集成测试的主要目的是保证单元______的完整性、一致性，人机界面及各种通信接口能否满足设计等要求。
p型半导体是在本征半导体中掺入三价元素硼构成的，其多数载流子是______。
已知某一线性电位器的测量位移原理如图所示。若电位器的总电阻R＝2kΩ，电刷位移为χ时的相应电阻Rχ＝1kΩ，电位器的工作电压Ui＝12V，负载电阻为RL。(1)已测得输出电压Uo＝5．8V，求RL。(2)试计算此时的测量误差。
利用一元线性回归模型预测的基本思路是先根据x、y的历史数据，求出________的值，建立起回归模型，再运用模型计算出不同的x所相对的不同的y值。
随机试题
关于非系统风险的说法正确的是()
A．280nmB．蛋白质分子颗粒大小在1～100nm之间C．特定的空间构象被破坏，理化性质丧失D．260nmE．在一定条件下可解离成带正电荷或负电荷的基团蛋白质的胶体性质
脱疽血瘀证特点为脱疽寒湿证特点为
平原地区建水闸，其基坑降排水的目的主要有()。
(2002年考试真题)根据我国《上市公司证券发行管理办法》的规定，上市公司发行的可转换公司债券在发行结束()后，方可转换为公司股票。
提供给与过世者关系密切的照顾者的服务属于()。
外部效应是指当事人的经济行为会给社会上其他成员带来好处，但他自己不能由此得到补偿，即当事人从其行为中得到的私人效益小于该行为带来的社会效益。下列属于正外部效应的是：
董仲舒
被杜威称为“教育史上的哥白尼式的革命”主要指的是
______beforewedepartthedayaftertomorrow,weshouldhaveawonderfuldinnerparty.
最新回复
(
0
)
