首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
admin
2014-12-25
37
问题
对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
选项
答案
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
数据结构导论
理工类
相关试题推荐
用奈奎斯特稳定性判据判别系统稳定的充要条件是z=p－N=0，其中p表示
设系统开环传递函数为G(s)=1+0．3s，其【】
开环传递函数G(s)H(s)=为【】系统。
简述差分曼彻斯特码的编码规则，并给出与题26图所示差分曼彻斯特码信号波形相对应的比特串(设线路的初始电平为-E)。
IPv4将IP地址没置为【】
在概念、结构和网络设计方面，都为后继的计算机网络技术发展起了重要作用的网络是【】
操作系统中的接口分为用户接口和_______两大类。
以太网中采用______作为介质控制访问方法。
常用的Internet安全协议包括Internet安全协议(IPsec)、______和运输层安全协议(TLS)等。
关系数据库中用来存储数据的对象是_______。
随机试题
下列各项引起胰腺炎的病因中，错误的是
按照建设工程项目总进度目标论证的工作步骤，在调查研究和收集资料后应进行的步骤是()。
Scientistshavefoundanewuseforchildren’simaginations—tomakestomachachesgoaway.TheBBCreportsanewstudythat
很多医学专家提出过量饮用咖啡对健康有害。为验证过量饮用咖啡对心脏的影响，研究人员选取了两组被试者。第一组被试者每天饮用5杯或5杯以上咖啡，第二组被试者从不饮用咖啡。一段时间后发现，第一组被试者中患心脏病的比例明显高于第二组被试者。因此，研究人员得出结论，过
社会化就是由自然人到社会人的转变过程，每个人必须经过社会化才能使外在于自己的社会行为规范、准则内化为自己的行为标准。再社会化是正常的社会化不完全或失败后重新开始的社会化过程。通过再社会化，可以全面地改变原有的价值观和生活方式，重新塑造出新的价值观和生活方式
新闻媒介是沟通社会与政府的重要桥梁，在政务信息传输系统中具有________的作用。但体制转型的压力，加之巨大利益的诱惑及制度缺失，给记者的职业操守带来巨大________，各种虚假报道不时见诸报端，成为小道消息的渊薮。因此我们必须不断完善新闻从业人员资格
你一个同事因为和你意见不一发生了正面冲突，事后你去找他道歉，他还很有抵触情绪。你该怎么办？
明朝创设的耻辱刑是______。
对于逻辑表达式“xandyornotz”，and、or、not分别是逻辑与、或、非运算，优先级从高到低为not、and、or，and、or为左结合，not为右结合，若进行短路计算，则_____________。
Mostrunners,whetherthey’retrainingforamarathonorsimplyouttogetsomeexercise,willstretchbeforetheytakeoff.It’
最新回复
(
0
)
