软考中级
对n个元素进行快速排序时，最坏情况下的时间复杂度为______。A．B．C．D．
题目
对n个元素进行快速排序时，最坏情况下的时间复杂度为______。
A．
B．
C．
D．
相似问题和答案
第1题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为______。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。其时间复杂度为0(n2)。
第2题：
● 对 n 个元素的数组进行 （63） ，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。
（63）
A. 希尔排序
B. 快速排序
C. 堆排序
D. 选择排序
第3题：
对n个元素进行堆排序时，最坏情况下的时间复杂度为(53)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：堆排序性能比较稳定，即使在最坏情况下的时间复杂度也是O(nlog2n)。
第4题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(65)。
A．O(log2n)
B．O(n)
C．O(nlog2/t)
D．O(n2)
解析：比较常用的排序算法的平均时间复杂度，以及最坏情况下的时间复杂度，可以知道快速排序最坏情况下的时间复杂度为O(n2)。
第5题：
假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度(用 O记号)。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n)，得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时，即长度为n的数组划分后一个子数组为n-1，一个为0，算法为最坏情况，此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n)，得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂，假设数组每次划分为9/10：1/10，此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)，得到时间复杂度为O(nlogn)，因此在平均情况下快速排序仍然有较好的性能，时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为n-1和0的两个子数组，属于最坏情况。
第6题：
对n个元素的数组进行(63)，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。
A．希尔排序
B．快速排序
C．堆排序
D．选择排序
解析：本题考查排序算法。
希尔排序的时间复杂度约为O(n1.4)。
快速排序在最坏情况下的时间复杂度为O(n2)。
选择排序的时间复杂度为O(n2)。
无论在什么情况下，堆排序的时间复杂度都是O(nlogn)。
第7题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(55)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：快速排序在最坏情况下的时间复杂度退化到一般的交换排序，即为O(n2)。
第8题：
此题为判断题(对，错)。
第9题：
对n个元素的数组进行()，其平均时间复杂度和最坏情况下都为O(nlogn)。
A.希尔排序
B.快速排序
C.堆排序
D.选择排序