1、二分搜索算法将分治的2个子问题减少为1个，时间复杂度由n降低为logn

题目

1、二分搜索算法将分治的2个子问题减少为1个，时间复杂度由n降低为logn

相似考题

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

2.●直接选择排序的平均时间复杂度为 (46) 。(46) A．O(n)B．O(nlogn)C．O(n2)D．O(logn)

3.假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n，T(1)=1表示，则该算法的时间复杂度为()A.O(logn)B.O(n*logn)C.O(n)D.O(n^2)

4.在有序双向链表中定位删除一个元素的平均时间复杂度为()A.O(1)B.O(N)C.O(logN)D.O(N*logN)

更多“1、二分搜索算法将分治的2个子问题减少为1个，时间复杂度由n降低为logn”相关问题

  • 第1题：

    已知一个大小为n的整型数组，现求该数组的全部连续子数组的元素之和的最大值，最优算法的时间复杂度是()如：a[4]={2,-1,3,-4}，它的全部连续子数组为{2,-1,3,-4,[2,-1],[-1,3],[3,-4],[2,-1,3],[-1,3,-4],[2,-1,3,-4]}，它们的元素之和为{2,-1,3,-4,1,2,-1,4,-2,0}，其中的最大值为4。

    A.O(logN)

    B.O(N)

    C.O(N*logN)

    D.O(N^2)


    正确答案：B

  • 第2题：

    二分查找树里查询一个关键字的最坏时间复杂度是______

    A.O(n)

    B.O(nlogn)

    C.O(logn)

    D.不确定


    正确答案：A

  • 第3题：

    某算法的语句执行频度为(3n2logn＋n3＋8),其时间复杂度是O(n3)()

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


    参考答案：正确

  • 第4题：

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

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


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

  • 第5题：

    某算法的空间花费s(n)=100nlog2n+0.5logn+1000n+2000，其空间复杂度为 ______.

    A．0(1)

    B．0(n)

    C．0(n1.5)

    D．0(nlog2n)


    正确答案：D

  • 第6题：

    向一个长度为N的顺序表中插入—个新元素的平均时间复杂度为(25)。

    A．O(N)

    B．O(1)

    C．O(logN)

    D．O(N2)


    正确答案：A
    解析：向一个长度为N的顺序表中插入一个新元素的平均比较次数为N/2，所以平均时间复杂度为O(N)。

  • 第7题：

    若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。

    A．O(n2)

    B．O(n)

    C．O(logn)

    D．O(nlogn)


    正确答案：C
    解析：本题考查的是算法消耗的时间度量。一般情况下，一个算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题n的增大，算法执行时间的增长率和　f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。显然，在O(n2)、O(n)、　O(logn)和O(nlogn)中，复杂度最小的是O(logn)。

  • 第8题：

    以下程序是用来计算两个非负数之间的最大公约数我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O(1)，那么该程序的时间复杂度为()

    A.O(1)

    B.O(logn)

    C.O(n)

    D.O(n^2)


    正确答案：C

  • 第9题：

    下面程序中算法的时间复杂度是()

    A.O(n)

    B.O(n^2)

    C.O(logn)

    D.O(n*logn)


    正确答案：C

  • 第10题：

    ●(37)有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为(37)。

    (37)A.O(1)

    B. O(logn)

    C.O(n)

    D. O(n2)


    正确答案：C

  • 第11题：

    填空题
    排序的平均时间复杂度为O（n•logn）的算法是（），为O（n•n）的算法是（）

    正确答案： 快速排序、二路归并排序、堆排序,直接插入排序、简单选择排序、起泡排序
    解析： 暂无解析

  • 第12题：

    多选题
    数据结构中，下列时间复杂度复杂度高低比较正确的是（）。
    A

    O(2^n)< O(n!)其中2^n表示2的n次幂

    B

    O(n)< O(nlogn)

    C

    O(n)>O(logn)

    D

    O(n!)


    正确答案： A,B
    解析： 暂无解析

  • 第13题：

    使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()

    A.O(N)

    B.O(logN)

    C.O(N*N)

    D.O(N*logN)


    正确答案：B

  • 第14题：

    类比二分搜索算法，设计A分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，...，这样，或者找到要搜索的元素，或者把集合缩小到原来的1／k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此A分搜索算法在最坏情况下搜索成功的时间复杂度为(1)，在最好情况下搜索失败的时间复杂度为(2)。

    A．O(logn)

    B．O(nlogn)

    C．O(logkn)

    D．O(nlogkn)


    正确答案：C
    解析：与二分法查找类似，k分查找法可用k叉树来描述。k分查找法在查找成功时进行比较的关键个数最多不超过树的深度，而具有n个结点的k叉树的深度为[logkn(k+1)]+　1，所以，k叉查找法在查找成功时和给定值进行比较的关键字个数至多为[logkn]+1，即时间复杂度为O(logkn)。同时，k分查找法在杳找不成功时，与给定值进行比较的关键字个数也至多为[logkn(k+1)]+1，即时间复杂度为O(logkn)。

  • 第15题：

    直接插入排序在最好情况下的时间复杂度为()。

    A、O(logn)

    B、O(n)

    C、O(n*logn)

    D、O(n2)


    正确答案：D

  • 第16题：

    某算法的空间花费s(n)=100nlog2n+0.5 logn+ 1000n+2000，其空间复杂度为______ 。

    A．0(1)

    B．0(n)

    C．0(n1.5)

    D．0(nlog2n)


    正确答案：D

  • 第17题：

    ● 有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为( )。

    A. O(1)

    B. O(logn)

    C. O(n)

    D. O(n2)


    正确答案：C

  • 第18题：

    ● 若某算法在问题规模为 n 时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为 （64） 。

    （64）A. O(n) B. O(n2) C. O(logn) D. O(nlogn)


    正确答案：B

  • 第19题：

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

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C

  • 第20题：

    给定下列代码：已知n是一个整数：foo()时间复杂度为O(1)，上述代码的时间复杂度是()

    A.O(logn)

    B.O(n)

    C.O(n*log(n))

    D.O(log(n)^2)


    正确答案：B

  • 第21题：

    类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，……，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(57)，在最好情况下搜索失败的时间复杂度为(58)。

    A．O(logn)

    B．O(nlogn)

    C．O(logkn)

    D．O(nlogkn)


    正确答案：C

  • 第22题：

    排序的平均时间复杂度为O（n•logn）的算法是（），为O（n•n）的算法是（）


    正确答案:快速排序、二路归并排序、堆排序；直接插入排序、简单选择排序、起泡排序

  • 第23题：

    单选题
    插入排序是一种简单实用的工具，在对数组排序时，我们可能用二分查找，对要插入的元素快速找到在已经排好元素序列中的位置。下面的描述中正确的是（）。
    A

    二分查找的时间复杂度为O（lgN），因此排序的时间复杂度为O（N*lgN）

    B

    二分查找的时间复杂度为O（N），因此排序的时间复杂度为O（N*lgN）

    C

    二分查找的时间复杂度为O（lgN），因此排序的时间复杂度为O（N*N）

    D

    二分查找的时间复杂度为O（N），因此排序的时间复杂度为O（N*N）


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

  • 第24题：

    单选题
    直接插入排序在最好情况下的时间复杂度为（  ）。
    A

    O（logn）

    B

    O（n）

    C

    O（n*logn）

    D

    O（n²）


    正确答案： D
    解析：

相关内容