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

admin2014-12-25 61

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

选项

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

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

转载请注明原文地址:https://kaotiyun.com/show/2iVx777K

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

数据结构导论

理工类

相关试题推荐

随机试题

最新回复(0)

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

数据结构导论

理工类

系统开环传递函数为【】的单位反馈系统，在输入xi(t)=1+4t作用下的稳态误差为0。

系统对单位斜坡函数输入R(s)=的稳态误差称为【】

时分多路复用可分为同步时分多路复用和异步时分多路复用，若时隙与用户(或各路信号)之间没有固定的对应关系，必须在用户数据中加上用户的标识，以标记是哪个用户的数据，则称为______。

UNIX网络操作系统的一个最突出特点就是_______。

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

软件测试的方法可分为两大类：_____测试和机器测试。

下列关于数据库的说法中不正确的是()

关系模型和层次、网状模型的最大区别是用________而不是指针导航数据，表格简单，用户易懂，编程时不涉及数据的物理结构。

铸铁气焊用气焊熔剂的牌号是()。

符合神经组织再生的描述是

A．胃、十二指肠溃疡穿孔B．急性胰腺炎C．胆道蛔虫症D．腹型癫痫E．幽门梗阻中上腹持续性剧痛，阵发性加剧

依据《中华人民共和国环境保护法》，对重要的水资源涵养区域，应当采取措施加以保护，严禁破坏。该行为的法律责任主体是()。

按照我国现行规定，以下工程建设项目中必须进行招标的有：()。

下列各项，可以通过资产负债表反映的是()。

东南亚国家和地区高等学校招生主要实行()。

去年国庆期间某旅游景点一天的时间盈利为200万元。今年该旅游景点预计，国庆期间盈利1000万没有问题。以下哪项最能支持上述推理?

某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。

下列关于视图的说法中，不正确的叙述是()。