itgle.com

某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(请作答此空),若问题的规模增加了16倍,则运行时间增加( )倍。A.O(n) B.O(nlgn) C.O(n2) D.O(n2lgn)

题目
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(请作答此空),若问题的规模增加了16倍,则运行时间增加( )倍。

A.O(n)
B.O(nlgn)
C.O(n2)
D.O(n2lgn)

相似考题
更多“某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(请作答此空),若问题的规模增加了16倍,则运行时间增加( )倍。A.O(n) B.O(nlgn) C.O(n2) D.O(n2lgn)”相关问题
  • 第1题:

    某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。

    A.O(n)

    B.

    C.O(n2)

    D.O(1)


    正确答案:B
    解析:由时间代价严格推出时间复杂度比较复杂,对于这种题,可用特例验证,不过需要注意的是特例不能取太少,至少n取到5,这样规律基本就可以确定了。
      T(1)=1
      T(2)=2T(1)+2=4
      T(3)=2T(1)+3=5
      T(4)=2T(2)+4=12
      T(5)=2T(2)+5=13
      很容易排除D选项,其递增速率介于O(n)和O(nsup>2</sup>)之间,故选B。

  • 第2题:

    下列程序段的时间复杂度为()。

    A.O(n)

    B.O(n-1)

    C.O(n2)

    D.O(log2n)


    正确答案:B

  • 第3题:

    若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)。

  • 第4题:

    对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(62);若采用快速排序算法,则时间和空间复杂度分别为(63)。

    A.O(n2)和O(n)

    B.O(n)和O(n)

    C.O(n2)和O(1)

    D.O(n)和O(1)


    正确答案:C
    本题考查基本排序算法的时间复杂度与空间复杂度。

  • 第5题:

    设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n>O)及T(0)=1,则该算法的时间复杂度为(65)。

    A.O(lgn)

    B.O (nlgn)

    C.O(n)

    D.O(n2)


    正确答案:D
    解析:本题考查算法设计基础知识。根据题目中给出的递推关系:T(n)=T(n-1)+n=T(n-2)+n-1+n=…=T(0)+1+2+…+n-1+n=1+n(n+1)/2

  • 第6题:

    设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为____。

    A.O(1)

    B.O(n)

    C.O(n2)

    D.O(log2n)


    正确答案:D

  • 第7题:

    设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示,则该算法的时间复杂度为(1)。

    A.O(lgn)

    B.O(nlgn)

    C.O(n)

    D.O(n2)


    正确答案:B
    解析:运用数学递推公式,可以推算出数量级O(nlgn)。

  • 第8题:

    求最短路径的FLOYD算法的时间复杂度为(16)。

    A.O(n)

    B.O(n+e)

    C.O(n2)

    D.O(n3)


    正确答案:D
    解析:FLOYD算法的时间复杂度为n3。

  • 第9题:

    某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用( )排序算法最好,时间复杂度为(请作答此空)。

    A.O(n)
    B.O(nlgn)
    C.O(n^2)
    D.O(n^2lgn)

    答案:C
    解析:
    当一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到插入排序法,时间复杂度为O(n^2),是稳定的排序方法。

  • 第10题:

    某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(62),若问题的规模增加了16倍,则运行时间增加(63)倍。

    A.16
    B.64
    C.256
    D.1024

    答案:C
    解析:
    对于递归式,假设T(1)=1,则:
    T(n)=T(n-1)+n
    =T(n-2)+n-1+n
    =T(n-3)+n-2+n-1+n
    =1+2+…+n-1+n
    =n(n+1)/2
    可见,时间复杂度为O(n2)。若问题的规模增加了16倍,则运行时间增加了162=256倍。

  • 第11题:

    已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,则该算法的时间复杂度为( )

    A.θ(n)
    B.θ(nlgn)
    C.θ(n2)
    D.θ(n3)

    答案:D
    解析:
    本题需要用到特定形式的递归式分析法:
    在本题中,a=8,b=2,故符合(1)的情况。时间复杂度为:O(n3)。a=16,b=4

  • 第12题:

    某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(62),若问题的规模增加了16倍,则运行时间增加(63)倍。

    A.O(n)
    B.O(nlgn)
    C.O(n2)
    D.O(n2lgn)

    答案:C
    解析:
    对于递归式,假设T(1)=1,则:
    T(n)=T(n-1)+n
    =T(n-2)+n-1+n
    =T(n-3)+n-2+n-1+n
    =1+2+…+n-1+n
    =n(n+1)/2
    可见,时间复杂度为O(n2)。若问题的规模增加了16倍,则运行时间增加了162=256倍。

  • 第13题:

    一个算法的语句执行次数为(2n2+2nlog2n+4n-7),则其时间复杂度为()。

    A.O(n2)

    B.O(nlog2n)

    C.O(n)

    D.O(2n2)


    正确答案:A

  • 第14题:

    下面算法的时间复杂度为(34)。 int f(unsigned int n){ if(n=0||n==1)return 1; else return n*f(n-1); }

    A.O(1)

    B.O(n)

    C.O(n2)

    D.O(n!)


    正确答案:B
    解析:连同其他函数调用f和f递归调用次数,计算f(n)需要执行n次函数调用。

  • 第15题:

    (接上一题)则时间和空间复杂度分别为(63)。

    A.O(n2)和O(n)

    B.O(nlgn)和O(n)

    C.O(n2)和O(1)

    D.O(nlgn)和O(1)


    正确答案:B
    同上一题解析

  • 第16题:

    计算N!的递归算法如下,求解该算法的时间复杂度时,只考虑相乘操作,则算法的计算时间T(n)的递推关系式为(55);对应时间复杂度为(56)。

    int Factorial (int n)

    {//计算n!

    if(n<=1)return 1;

    else return n * Factorial(n-1);

    }

    (62)

    A.T(n)=T(n-1)+1

    B.T(n)=T(n-1)

    C.T(n)=2T(n-1)+1

    D.T(n)=2T(n-1)-1


    正确答案:A

  • 第17题:

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

    A.O(n)

    B.O(n2)

    C.O(logn)

    D.O (nlogn)


    正确答案:B
    解析:T(n)=T(n-1)+n=T(n-2)+n-1+n=……=T(1)+n+(n-1)+(n-2)+……+2=n(n+1)/2,时间复杂度为0(n2。)。

  • 第18题:

    下面算法的时间复杂度为()

    A.O(1)

    B.O(n)

    C.O(n*n)

    D.O(n!)


    正确答案:B

  • 第19题:

    在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为( ),若问题的规模增加了16倍,则运行时间增加( )倍。

    A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn) A.16 B.64 C.256 D.1024


    正确答案:C,C

  • 第20题:

    设图G采用邻接表存储,则拓扑排序算法的时间复杂度为( )

    A.O(n)

    B.O(n+e)

    C.O(n2)

    D.O(n×e)


    正确答案:B

  • 第21题:

    给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x,先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=1;high=n;while(high>low)if A[low]+A[high]=x return true;else if A[low]+A[high]>x low++;else high--;return false;则过程P的时间复杂度为( ),整个算法的时间复杂度为(请作答此空)。

    A.O(n)
    B.O(nlgn)
    C.O(n2)
    D.O(n2lgn)

    答案:C
    解析:
    本题考查时间复杂度的基本知识。第一空有一层循环while,遍历判断,所以时间复杂度为n;第二空如图所示:插入排序的时间复杂为O(n2) ;故第一空正确答案为A;第二空正确答案为C;

  • 第22题:

    某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为( ),若问题的规模增加了16倍,则运行时间增加(请作答此空)倍。

    A.16
    B.64
    C.256
    D.1024

    答案:C
    解析:
    对于递归式,假设T(1)=1,则:T(n)=T(n-1)+n=T(n-2)+n-1+n=T(n-3)+n-2+n-1+n=1+2+…+n-1+n=n(n+1)/2可见,时间复杂度为O(n2)。若问题的规模增加了16倍,则运行时间增加了162=256倍。

  • 第23题:

    设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n>O)及T(0)=1,则该算法的时间复杂度为( )。

    A.O(lgn)
    B.O(nlgn)
    C.O(n)
    D.O(n^2)

    答案:D
    解析:
    本题考查算法设计基础知识。根据题目中给出的递推关系:T(n)=T(n-1)+n=T(n-2)+n-1+n=…=T(0)+1+2+…+n-1+n=1+n(n+1)/2