违法和不良信息举报 联系客服
免费注册 登录

对n个元素的数组进行(),其平均时间复杂度和最坏情况下都为O(nlogn)。A.希尔排序B.快速排序C.堆排

题目

对n个元素的数组进行()，其平均时间复杂度和最坏情况下都为O(nlogn)。

A.希尔排序

B.快速排序

C.堆排序

D.选择排序

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

在希尔排序、归并排序、快速排序和堆排序中，最好和最坏情况下的时间复杂度均为O（nlogn)且稳定的排序方法是__________排序。


正确

第2题：

关于快速排序的时间复杂度，（)是正确的。

A．在最坏情况下时间复杂度为O(n^2)

B．在最好情况下时间复杂度为O(nlogn)

C．在平均情况下时间复杂度为O(n^2)

D．在平均情况下时间复杂度为O(nlogn)


n2

第3题：

快速排序算法平均时间复杂度和最坏时间复杂度均为O（nlogn)。


C

第4题：

● 对 n 个元素的数组进行 （63） ，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。

（63）

A. 希尔排序

B. 快速排序

C. 堆排序

D. 选择排序


正确答案：C

第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的两个子数组属于最坏情况。
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式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．选择排序


正确答案：C
解析：本题考查排序算法。
  希尔排序的时间复杂度约为O(n1.4)。
  快速排序在最坏情况下的时间复杂度为O(n2)。
  选择排序的时间复杂度为O(n2)。
  无论在什么情况下，堆排序的时间复杂度都是O(nlogn)。

第7题：

对n个数进行排序，哪种算法，其时间复杂度在最坏和最好都是O(nlogn)()

A.快速排序

B.希尔排序

C.堆排序

D.选择排序


正确答案：C

第8题：

关于排序算法的以下说法，错误的是()

A.归并排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)

B.堆排序平均时间复杂度O(nlogn)，最坏时间复杂度O(nlogn)

C.冒泡排序平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)

D.快速排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)


正确答案：A

第9题：

对n个记录的序列进行堆排序,最坏情况下的时间复杂度为______。

A、O(logn)

B、O(nlogn)

C、O(n)

D、O(n^2)


正确答案：B

相关内容