单选题基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是（ ）。A O（nlogn）B O（logn）C O（n）D O（n*n）

题目
单选题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是（  ）。
A

O（nlogn）

B

O（logn）

C

O（n）

D

O（n*n）

相似考题

1.下列排序方法中,在最坏情况下算法的时间复杂度为 O(n^2)的有________。A、堆排序B、快速排序C、希尔排序D、冒泡排序

2.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序。()此题为判断题(对，错)。

3.最好和最坏时间复杂度均为O(nlog2n)且稳定的排序方法是()。A.快速排序B.堆排序C.归并排序D.基数排序

4.对n个记录的序列进行堆排序,最坏情况下的时间复杂度为______。A、O(logn)B、O(nlogn)C、O(n)D、O(n^2)

参考答案和解析
正确答案： C
解析：
更多“基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是（  ）。”相关问题

  • 第1题：

    ●以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是 (33) ；该算法采用的设计方法是 (34) 。

    (33) A．归并排序

    B．插入排序

    C．选择排序

    D．冒泡排序

    (34) A．分治法

    B．贪心法

    C．动态规划方法

    D．回溯法


    正确答案：A,A
    【解析】归并排序(merge sort)，是把待排序的文件分成n个已排序的子文件，将这些文件合并得到完全排序的文件。n个记录的平均运算次数是O(nlog2n)，所需的辅助存储空间是O(n)，该算法采用的设计方法是分治法。

  • 第2题：

    下列排序方法中,最坏情况下时间复杂度(即比较次数)低于o(n2)的是()。

    A.堆排序

    B.快速排序

    C.简单插入排序

    D.冒泡排序


    正确答案：A

  • 第3题：

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

    A.希尔排序

    B.快速排序

    C.堆排序

    D.选择排序


    正确答案：C

  • 第4题：

    在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(51)。

    A．基数排序

    B．快速排序

    C．堆排序

    D．归并排序


    正确答案：D
    解析：基数排序最坏的时间复杂度均为O(d(n+rd))；快速排序最好和最坏情况下F的时间复杂度分别为O(n2)和O(nlogn)且不稳定；堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定；归并排序是在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法。

  • 第5题：

    关于冒泡排序,说法正确的是()

    A、稳定的

    B、不稳定的

    C、是一种交换排序方法

    D、最坏情况下的时间复杂度是O(n2).


    参考答案：ACD

  • 第6题：

    对于n个记录的集合进行冒泡排序,在最坏情况下时间复杂度是O(n2)()

    此题为判断题(对，错)。


    参考答案：对

  • 第7题：

    假设要排序包含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的两个子数组，属于最坏情况。

  • 第8题：

    对N个数排序,最坏情况下时间复杂度最低的算法是()排序算法

    A、插入

    B、冒泡

    C、归并

    D、快速


    正确答案：C

  • 第9题：

    任何一个基于比较的内部排序算法，若对 6个元素进行排序，最坏情况下所需要的比较

    次数是几次。


    正确答案：
     

  • 第10题：

    以关键字比较为基础的排序算法在最坏情况下的计算时间下界为

    O(nlogn)。下面的排序算法中，在最坏情况下计算时间可以达到

    O(nlogn)的是( 58 )；

    A.归并排序

    B.插入排序

    C.选择排序

    D.冒泡排序


    正确答案：A
    记忆几类常见的排序算法的时间复杂度即可。

  • 第11题：

    在最好和最坏情况下的时间复杂度均为0(nlogn)且稳定的排序方法是()。

    A.基数排序
    B.归并排序
    C.快速排序
    D.堆排序

    答案：B
    解析：
    快速排序和堆排序是不稳定的，基数排序和归并排序是稳定的。基数排序的平均时间为O(d(n+rd))，最坏情况下时间复杂度为O(d(n+rd))；归并排序是一种稳定的排序方法，其最好和最坏情况下的时间复杂度为O(nlogn)。

  • 第12题：

    单选题
    快速排序在最坏情况下的时间复杂度是（  ）。
    A

    O（nlogn）

    B

    O（n2）

    C

    O（n）

    D

    O（n）


    正确答案： B
    解析：

  • 第13题：

    ●在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是 (52) 。

    (52) A．快速排序

    B．堆排序

    C．归并排序

    D．基数排序


    正确答案：C
    【解析】快速排序和堆排序都是不稳定的排序方法；归并排序和基数排序则是稳定的排序方法，基数排序的时间复杂度为O(d(n+r))(其中n为记录数，r为基数，d为关键字分量数)，归并排序的时间复杂度在最好和最坏情况下均为O(nlog2n)。

  • 第14题：

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

    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

  • 第15题：

    最坏情况下时间复杂度不是n(n-1)/2的排序算法是()

    A.快速排序

    B.冒泡排序

    C.直接插入排序

    D.堆排序


    正确答案：D

  • 第16题：

    以比较为基础的排序算法在最坏情况下的计算时间下界为(55)。

    A．O(n)

    B．O(n2)

    C．O(logn)

    D．O(nlogn)


    正确答案：D
    解析：此问题考查以比较为基础的排序算法的时间复杂度分析，利用二元树可以证明对任何以关键字比较为基础的排序算法，最坏情况的计算时间下界都为O(nlogn)，如归并排序算法。

  • 第17题：

    对于n个记录的集合进行快速排序,在最坏的情况下时间复杂度是O(n2)()

    此题为判断题(对，错)。


    参考答案：错

  • 第18题：

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

    A．希尔排序

    B．快速排序

    C．堆排序

    D．选择排序


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

  • 第19题：

    以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是(59)；该算法采用的设计方法是(60)。

    A．归并排序

    B．插入排序

    C．选择排序

    D．冒泡排序


    正确答案：A
    解析：直接插入排序、简单选择排序和冒泡排序最坏情况下计算时间可以达到O(n2)，而归并排序的时间最坏情况下可以达到O(nlogn)。而归并排序也是分治策略的一个典型应用。

  • 第20题：

    对n个元素进行快速排序时，最坏情况下的时间复杂度为______。

    A．

    B．

    C．

    D．


    正确答案：D
    解析：各种排序算法性能比较如下：

  • 第21题：

    直接选择排序的平均时间复杂度为(17)。最好情况下时间复杂度为O(n)的排序算法是(18)。在最好和最花情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(19)。

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C

  • 第22题：

    以关键字比较为基础的排序算法在最坏情况下的汁算时间下界为O(n1ogn)。下面的排序算法中，最坏情况下计算时间可以达到O(n1ogn)的是(33)；该算法采用的设计方法是(34)。

    A．归并排序

    B．插入排序

    C．选择排序

    D．冒泡排序


    正确答案：A
    解析：归并排序(mergesort)，是把待排序的文件分成n个已排序的子文件，将这些文件合并得到完全排序的文件。n个记录的平均运算次数是O(nlog2n)，所需的辅助存储空间是O(n)，该算法采用的设计方法是分治法。

  • 第23题：

    以比较为基础的排序算法在最坏情况下的计算时间下界为()。


    答案：D
    解析：

相关内容