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

admin2014-12-25 26

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

选项

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

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

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

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

数据结构导论

理工类

相关试题推荐

随机试题

最新回复(0)

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

数据结构导论

理工类

一系统在扰动作用下的误差函数为EN(s)=，则系统由扰动引起的稳态误差essN等于【】

B类IP地址，网络号的最高两位固定为二进制________。

【】的主要功能是实现在相邻结点之间的数据町靠而有效地传输。

______是指接收到的错误码元数在所传输的总码元数中所占的比例。

IP采用_____作为网络互联的中间设备，其作用是将不同的计算机网络连接在一起，在网络层实现数据的路由和转发。

在IP数据报中，总长度字段占【】位。

下列常用的网络性能测评指标中，属于面向服务的性能指标的是【】

考虑一个有760个字节程序的如下存储器引用：12，90，351，190，180，475，30，550，635，650，227，430，640，710，745，10，15，650，740，249(1)假定主存中每块为100个字节，对于以上的存储器引用序列

当集成运放工作在线性区时，下面的说法正确的是【】

网络图的结点符号是在圆圈的上半方标以________；下半部分的左侧标以该结点(事项)的最早开始时间值，右侧标以该结点(事项)的最迟完成时间值。

Notuntilmostofthepeoplehadleftthemeetingroom________hissisterwasthere.

正常人消化道内铁吸收效率最高的部位是

社区卫生服务的目的是

类实验与一般流行病学实验研究比较有哪些特点

发行公司债券和股份是公司筹措资金的两种主要手段，依据《公司法》的规定，两者相比，有以下哪些区别?()

商品最本质的因素是()。

【2014年湖南郴州／2013年福建】我国现在实行的义务教育的年限是()。

下列选项中属于无效民事行为的有（）。

公安机关要当好党委的()

有以下程序main(){　char　s[]="\n123\\";printf("%d,%d\n",strlen(s),sizeof(s));}执行后输出结果是

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

数据结构导论

理工类

一系统在扰动作用下的误差函数为EN(s)=，则系统由扰动引起的稳态误差essN等于【】

B类IP地址，网络号的最高两位固定为二进制________。

【】的主要功能是实现在相邻结点之间的数据町靠而有效地传输。

______是指接收到的错误码元数在所传输的总码元数中所占的比例。

IP采用_____作为网络互联的中间设备，其作用是将不同的计算机网络连接在一起，在网络层实现数据的路由和转发。

在IP数据报中，总长度字段占【】位。

下列常用的网络性能测评指标中，属于面向服务的性能指标的是【】

考虑一个有760个字节程序的如下存储器引用：12，90，351，190，180，475，30，550，635，650，227，430，640，710，745，10，15，650，740，249(1)假定主存中每块为100个字节，对于以上的存储器引用序列

当集成运放工作在线性区时，下面的说法正确的是【】

网络图的结点符号是在圆圈的上半方标以________；下半部分的左侧标以该结点(事项)的最早开始时间值，右侧标以该结点(事项)的最迟完成时间值。

Notuntilmostofthepeoplehadleftthemeetingroom________hissisterwasthere.

正常人消化道内铁吸收效率最高的部位是

社区卫生服务的目的是

类实验与一般流行病学实验研究比较有哪些特点

发行公司债券和股份是公司筹措资金的两种主要手段，依据《公司法》的规定，两者相比，有以下哪些区别?()

商品最本质的因素是()。

【2014年湖南郴州／2013年福建】我国现在实行的义务教育的年限是()。

下列选项中属于无效民事行为的有（）。

公安机关要当好党委的()

有以下程序main(){ char s[]="\n123\\";printf("%d,%d\n",strlen(s),sizeof(s));}执行后输出结果是

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

有以下程序main(){　char　s[]="\n123\\";printf("%d,%d\n",strlen(s),sizeof(s));}执行后输出结果是