对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。A、O(n)B、O(n2)C、O(nlog2n)D、O(n3)

题目

对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。

  • A、O(n)
  • B、O(n2
  • C、O(nlog2n)
  • D、O(n3

相似考题
更多“对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。”相关问题
  • 第1题:

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

    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

  • 第2题:

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

    A.希尔排序

    B.快速排序

    C.堆排序

    D.选择排序


    正确答案:C

  • 第3题:

    对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。

    A.O(n)

    B、O(n2)

    C、O(nlog2n)

    D、O(n3)


    参考答案:B
    解释:快速排序的平均时间复杂度为O(nlog2n),但在最坏情况下,即关键字基本排好序的情况下,时间复杂度为O(n2)。

  • 第4题:

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

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


    参考答案:错

  • 第5题:

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

    A.希尔排序

    B.快速排序

    C.堆排序

    D.选择排序


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

  • 第6题:

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

    A、插入

    B、冒泡

    C、归并

    D、快速


    正确答案:C

  • 第7题:

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

    A.归并排序

    B.插入排序

    C.选择排序

    D.冒泡排序


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

  • 第8题:

    快速排序在最坏情况下的时间复杂度为()。


    答案:D
    解析:

  • 第9题:

    对于n个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是()。若对其进行快速排序,在最坏的情况下所需要的时间是()。


    正确答案:O(n2);O(n2

  • 第10题:

    设初始记录关键字基本有序,则快速排序算法的时间复杂度为O(nlog2n)。


    正确答案:错误

  • 第11题:

    填空题
    对于n个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是()。若对其进行快速排序,在最坏的情况下所需要的时间是()。

    正确答案: O(n2),O(n2
    解析: 暂无解析

  • 第12题:

    单选题
    对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是()
    A

    O(n)

    B

    O(n2

    C

    O(nlog2n)

    D

    O(n3


    正确答案: B
    解析: 暂无解析

  • 第13题:

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

    A.快速排序

    B.希尔排序

    C.堆排序

    D.选择排序


    正确答案:C

  • 第14题:

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

    A.快速排序

    B.冒泡排序

    C.直接插入排序

    D.堆排序


    正确答案:D

  • 第15题:

    对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是()

    A. O(n)

    B. O(n2)

    C. O(nlog2n)

    D. O(n3)


    正确答案:B

  • 第16题:

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

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


    参考答案:对

  • 第17题:

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

  • 第18题:

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

    A.

    B.

    C.

    D.


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

  • 第19题:

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

    A.O(log2n)

    B.O(n)

    C.O(nlog2n)

    D.O(n2)


    正确答案:D
    解析:最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。其时间复杂度为0(n2)。

  • 第20题:

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

    A.插入
    B.冒泡
    C.归并
    D.快速

    答案:C
    解析:
    归并排序最好和最坏的情况下的时间复杂度都是(O)nlogn,而其他几个算法最坏情况下的时间复杂度是(O)n^2。

  • 第21题:

    快速排序在平均情况下的时间复杂度为(),在最坏情况下的时间复杂度为()。


    正确答案:O(nlog2n);O(n2

  • 第22题:

    填空题
    快速排序在平均情况下的时间复杂度为(),在最坏情况下的时间复杂度为()。

    正确答案: O(nlog2n),O(n2
    解析: 暂无解析

  • 第23题:

    单选题
    对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。
    A

    O(n)

    B

    O(n2

    C

    O(nlog2n)

    D

    O(n3


    正确答案: A
    解析: 快速排序的平均时间复杂度为O(nlog2n),但在最坏情况下,即关键字基本排好序的情况下,时间复杂度为O(n2)。

  • 第24题:

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

    O(nlogn)

    B

    O(n2)

    C

    O(n)

    D

    O(n)


    正确答案: B
    解析: