下列时间复杂度中最坏的是（）。A、O（1）B、O（n）C、O（log2n）D、O（n2）

题目

下列时间复杂度中最坏的是（）。

  • A、O（1）
  • B、O（n）
  • C、O（log2n）
  • D、O（n2）
相似考题

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

2.在最坏情况下，下列排序方法中时间复杂度最小的是______。A．冒泡排序B．快速排序C．插入排序D．堆排序

3.下列排序方法中，最坏情况下时间复杂度最低的是()。A.冒泡排序B.快速排序C.希尔排序D.堆排序

4.算法复杂度包括时间复杂度和空间复杂度。对空间复杂度一般可以用平均态和最坏情况复杂性来衡量：而对于空间复杂度，一般指执行该算法所需要的______。

更多“下列时间复杂度中最坏的是（）。”相关问题

  • 第1题：

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

    A.堆排序

    B.快速排序

    C.简单插入排序

    D.冒泡排序


    正确答案：A

  • 第2题：

    下列排序方法中，最坏情况下时间复杂度最小的是()。

    A.冒泡排序

    B.快速排序

    C.堆排序

    D.直接插入排序


    正确答案：C

  • 第3题：

    在最坏情况下，冒泡排序的时间复杂度为（ ）。


    正确答案：
    n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2)

  • 第4题：

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

    A、插入

    B、冒泡

    C、归并

    D、快速


    正确答案：C

  • 第5题：

    算法复杂度包括时间复杂度和空间复杂度。对于时间复杂度，一般可以用平均性态和最坏情况复杂性来衡量：对于空间复杂度，一般指执行该算法所需要的【 】。


    正确答案：内存空间
    内存空间

  • 第6题：

    设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是（）

    A.堆排序

    B.有序链表查找

    C.希尔排

    D.循环链表中寻找最大项


    正确答案：D

  • 第7题：

    在最坏情况下，冒泡排序的时间复杂度为________，简单插入排序的时间复杂度为________，希尔排序的时间复杂度为________，简单选择排序的时间复杂度为________，堆排序的时间复杂度为________。


    正确答案：
    O(n(n-1)/2)  O(n(n—1)/2)  O(n1.5) O(n(n—1)/2) O(nlog2n)

  • 第8题：

    对N个数排序，最坏情况下时间复杂度最低的算法是（ ）排序算法

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

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

  • 第9题：

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


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

  • 第10题：

    给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。


    正确答案: 我们把这种算法叫做快速选择（quickselect）。令〡Si〡为Si中元素的个数，快速选择的步骤如下：
    1）如果〡S〡=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且〡S〡≤CUTOFF，则将S排序并返回第k个最小元。
    2）选取一个枢纽元v∈S。
    3）将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。
    4）如果k≤〡S1〡，那么第K个最小元必然在S1中。在这种情况下，返回quickselect（S1，k），如果k=1+〡S1〡
    ，那么枢纽元就是第k个最小元，将它最为答案返回。否则，第k个最小元就在S2中，他是S2中的第（k-〡S1〡-1）个最小元。我们进行一次递归调用并返回quickselect（S2，k-〡S1〡-1）。
    与快速排序对比，快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同，也就是O（N=2）。直观看来，这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候；于是，快速选择也就不是真的节省一次递归调用。不过平均运行时间是O（N）。具体分析类似快速排序的分析。
    快速排序的实现甚至比抽象描述还要简单，当算法终止时，第k个最小元就在位置k-1上（因为数组开始于下标0）。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。

  • 第11题：

    填空题
    堆排序是不稳定，空间复杂度为（）。在最坏情况下，其时间复杂度也为（）

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

  • 第12题：

    单选题
    下列关于算法复杂度叙述正确的是（　　）。
    A

    最坏情况下的时间复杂度一定高于平均情况的时间复杂度

    B

    时间复杂度与所用的计算工具无关

    C

    对同一个问题，采用不同的算法，则它们的时间复杂度是相同的

    D

    时间复杂度与采用的算法描述语言有关


    正确答案： D
    解析：
    A项错误，最坏情况下的时间复杂度有可能与平均情况的时间复杂度相同；C项错误，对同一个问题，不同的算法时间复杂度有时可能差距很大；D项错误，算法的时间复杂度与实现算法的描述语言、运行环境无关，算法的时间复杂度是对算法执行时所花时间的度量。答案选择B选项。

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

    A．希尔排序

    B．快速排序

    C．堆排序

    D．选择排序


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

  • 第16题：

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

    A．

    B．

    C．

    D．


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

  • 第17题：

    在最坏情况下，二分查找法的时间复杂度为（ ）。


    正确答案：C
    二分法查找也称拆半查找，能使用二分1法查找的线性表必须满足两个条件，用顺序存储结构以及线性f表有序。利用二分法查找元素x的过程如下：将x与线性表1的中间项比较，如果X的值与中间项的值相等，则查找成功，1结束查找；如果x小于中间项的值，则在线性表的前半部分以二分法继续查找；如果x大于中间项的值，则在线性表的后半1部分以二分法继续查找。可以证明，对于长度为n的有序线性f表，在最坏情况下，二分法查找需比较l092n次，故时间复杂度1为l092n。故选择C选项。

  • 第18题：

    下列各排序法中，最坏情况下的时间复杂度最低的是( )。

    A.希尔排序

    B.快速排序

    C.堆排序

    D.冒泡排序


    参考答案：C参考解析：堆排序最坏情况时间下的时间复杂度为O(n1og2n);希尔排序最坏情况时间下的时间复杂度为O(n1.5);快速排序、冒泡排序最坏情况时间下的时间复杂度为O(n2)。故本题答案为C选项。

  • 第19题：

    以下有关算法的说法错误的是()。Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间；Ⅱ，在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法；Ⅲ.所谓最坏时间复杂度是指最坏情况下估算算法执行时间的一个上界；Ⅳ，同一个算法，实现语言的级别越高，执行效率就越低。

    A.Ⅰ
    B.Ⅰ和Ⅱ
    C.Ⅰ和Ⅳ
    D.Ⅲ

    答案：C
    解析：
    算法原地工作的含义是指算法的空间复杂度为O(1)，同一个算法实现语言的级别越高执行效率并不一定越低。

  • 第20题：

    DBSCAN在最坏情况下的时间复杂度是（）。

    • A、O（m）
    • B、O（m2）
    • C、O（logm）
    • D、O（m*logm）

    正确答案:B

  • 第21题：

    堆排序是不稳定，空间复杂度为（）。在最坏情况下，其时间复杂度也为（）


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

  • 第22题：

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

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

  • 第23题：

    单选题
    下列时间复杂度中最坏的是（）。
    A

    O（1）

    B

    O（n）

    C

    O（log2n）

    D

    O（n2）


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

相关内容