对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是__。

admin2014-12-25 25

问题对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。

选项

答案O(nlog₂n) O(n²)

解析快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需log₂n趟划分即可。每趟划分所需时间复杂度为O(n)，最好情况下的时间复杂度是O(nlog₂n)。
最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n一1趟划分。每趟划分的时间复杂度为O(n)，因此，最坏情况下的时间复杂度为O(n²)。

转载请注明原文地址:https://jikaoti.com/ti/8jLaFFFM

本试题收录于：数据结构导论题库理工类分类

数据结构导论

理工类

相关试题推荐

随机试题

最新回复(0)

对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是__。

数据结构导论

理工类

设系统开环传递函数为G(s)=1+0．3s，其【】

某闭环控制系统中，如果反馈回去的信号(或作用)与原系统的输入信号(或作用)的方向相反(或相位相差180°)，则称为________。

下面关于系统稳态误差的说法中，正确的是【】

下列属于管理信息库中的结构数据的是【】

______是指利用管理控制和技术措施，保证在计算机网络环境中，数据信息的机密性、完整性和可用性受到保护。

下列关于项目的说法，不正确的是()

下面不是T-SQL的流程控制语句的是()

下列不是DAC0832内部组成的是()

下列属于我国公务员的义务的是

Manyamanandawoman______himselforherselffacedwithamarriagecrisis.

肺部感染可形成空洞的疾病是

葡萄胎声像图上，出现多数直径在3～5mm无回声囊泡，最大可能是什么

治疗癫痫小发作的首选药物是()。

下列关于行业内竞争程度的说法，正确的有()。

法的适用是指()。

以下握手要领中，错误的是()。

用IE浏览器打开：http：//localhost：65531／ExamWeb／index．htm，浏览有关“OSPF路由协议”的网页，将该页内容以文本文件的格式保存到考生目录下，文件名为“TestIe．txt”。