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

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

admin2014-12-25  30
问题 对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。
选项
答案O(nlog2n) O(n2)
解析 快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需log2n趟划分即可。每趟划分所需时间复杂度为O(n)，最好情况下的时间复杂度是O(nlog2n)。
  最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n一1趟划分。每趟划分的时间复杂度为O(n)，因此，最坏情况下的时间复杂度为O(n2)。
转载请注明原文地址:https://kaotiyun.com/show/2iVx777K
本试题收录于： 数据结构导论题库理工类分类
0

数据结构导论

理工类

相关试题推荐
随机试题
最新回复(0)