itgle.com

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

题目

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

相似考题

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
更多“快速排序算法平均时间复杂度和最坏时间复杂度均为O（nlogn)。”相关问题

  • 第1题：

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

    (52) A．快速排序

    B．堆排序

    C．归并排序

    D．基数排序


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

  • 第2题：

    在最好和最坏情况下的时间复杂度均为O(nlogn)，但不稳定的排序算法是(60)。

    A．堆排序

    B．快速排序

    C．归并排序

    D．基数排序


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

  • 第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题：

    直接选择排序的平均时间复杂度为(46)。

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C
    解析：本题主要考查排序算法的时间复杂度。排序算法的时间复杂度是用元素的平均比较次数和元素的平均移动次数来衡量的，它是评价排序算法的主要标准。

  • 第6题：

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

    A、插入

    B、冒泡

    C、归并

    D、快速


    正确答案：C

  • 第7题：

    快速排序方法(Quick Sort)的时间复杂度为(61)。

    A．O(n2)

    B．O(nlogn)

    C．O(n)

    D．O(logn)


    正确答案：B
    解析：对长度为n的序列进行快速排序，设所需时间为T(n)，则可知T(n)=T(k-1)+T(n-k)+cn。cn表示对n个记录进行一趟快速排序所需的时间。递归即可得出快速排序方法(QuickSort)的时间复杂度为O(nlogn)。

  • 第8题：

    下列排序算法中，时间复杂度不受数据初始状态影响恒为O(nlogn)的是()。

    A.堆排序
    B.冒泡排序
    C.快速排序
    D.直接插入排序

    答案：A
    解析：
    堆排序和快速排序是O(nlogn)的复杂度，但是快速排序在数据初始状态有序的情况下蜕化为冒泡排序。

  • 第9题：

    给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。


    正确答案: 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
    1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j] 2、否则，m[i]=1+max{m[j]|x[j] 3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存在状态k∈S，使得m[i]=m[k]，则我们有x[i]x[i]，j∈S}。于是状态k应从S中删去。
    从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。

  • 第10题：

    下列各种排序算法中平均时间复杂度为O（n2）是（）

    • A、快速排序
    • B、堆排序
    • C、归并排序
    • D、冒泡排序

    正确答案:D

  • 第11题：

    单选题
    在任何情况下，时间复杂度均为O（nlogn）的不稳定的排序方法是（）。
    A

    直接插入

    B

    快速排序

    C

    堆排序

    D

    归并排序


    正确答案： C
    解析： 暂无解析

  • 第12题：

    问答题
    给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。

    正确答案： 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
    1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j] 2、否则，m[i]=1+max{m[j],x[j] 3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存在状态k∈S，使得m[i]=m[k]，则我们有x[i]x[i]，j∈S}。于是状态k应从S中删去。
    从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。
    解析： 暂无解析

  • 第13题：

    在最坏情况下()。

    A.快速排序的时间复杂度比冒泡排序的时间复杂度要小

    B.快速排序的时间复杂度比希尔排序的时间复杂度要小

    C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小

    D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的


    正确答案：C

  • 第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个元素的数组进行()，其平均时间复杂度和最坏情况下都为O(nlogn)。

    A.希尔排序

    B.快速排序

    C.堆排序

    D.选择排序


    正确答案：C

  • 第16题：

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

    A．希尔排序

    B．快速排序

    C．堆排序

    D．选择排序


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

  • 第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题：

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

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C

  • 第19题：

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

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

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

  • 第20题：

    数据结构与算法中，快速排序的特性描述正确的是（）。

    • A、快速排序是稳定排序
    • B、快速排序不稳定排序
    • C、快速排序的时间复杂度是O（nlog2n）
    • D、快速排序的时间复杂度是O（n*n）

    正确答案:B,C

  • 第21题：

    在任何情况下，时间复杂度均为O（nlogn）的不稳定的排序方法是（）。

    • A、直接插入
    • B、快速排序
    • C、堆排序
    • D、归并排序

    正确答案:C

  • 第22题：

    快速排序在平均情况下的时间复杂度为（），在最坏情况下的时间复杂度为（）。


    正确答案:O（nlog2n）；O（n2）

  • 第23题：

    填空题
    快速排序在平均情况下的时间复杂度为（），在最坏情况下的时间复杂度为（）。

    正确答案： O（nlog2n）,O（n2）
    解析： 暂无解析

  • 第24题：

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

    O（nlogn）

    B

    O（n2）

    C

    O（n）

    D

    O（n）


    正确答案： B
    解析：

相关内容