• 2022-07-28
    查看本试题中关于回文判断的算法题目,分析算法的时间复杂性,如下描述中正确的是哪个?
    A: 该算法时间复杂性的递归定义为: T(n)=T(n-1)+1,if n>1;T(n)=O(1),if n≤1。T(n)=O(n), T(n)=Ω(1)
    B: 该算法时间复杂性的递归定义为: T(n)=T(n-1)+1,ifn>1;T(n)=O(1),if n≤1。T(n)=O(n), T(n)=Ω(n)
    C: 该算法时间复杂性的递归定义为: T(n)=T(n-2)+1,if n>1;T(n)=O(1), if n≤1。T(n)=O(n), T(n)=Ω(1)
    D: 该算法时间复杂性的递归定义为: T(n)=T(n-2)+1,if n>1;T(n)=O(1), if n≤1。T(n)=O(n), T(n)=Ω(n)
  • C

    内容

    • 0

      设问题规模为N时,某递归算法的时间复杂度记为T(),已知T(1)=1,T()=2T(N/2)+N/2,用O表示的时间复杂度为()。 A: O(logN) B: O(N) C: O(NlogN) D: O(N²logN)

    • 1

      T(n)表示当输入规模为n时的算法效率,分治算法的一般模式是( )。 A: T(n)=T(n–1)+1,T(1)=1 B: T(n)=2n2 C: T(n/2)+n,T(1)=1 D: T(n)=3nlog2n

    • 2

      某算法的执行时间的递推关系如下:T(n)=1 当n=1时T(n)=2T(n/2)+1 当n>;1时则该算法的时间复杂度为( )。 A: O(1) B: O(log�) C: O(n) D: O(nlog�)

    • 3

      棋盘nxn([img=50x23]1803a65edbc3033.png[/img])的覆盖问题,其中一个点已经被覆盖,用L型模块将其余完全覆盖的分治算法。关于该算法时间复杂性描述不正确的是 A: T(n)=4T(n/2)+O(1) , if n>1; T(n)=O(1) ,if n==1 。 B: T(k)=4T(k-1)+O(1) , if k>0;T(k)=O(1) , if k==0。 这里n=2^k C: T(n)=O(n^4) D: T(k)=O(4^k)

    • 4

      某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为(53)。 A: O(n) B: O(nlog2n) C: O(n2) D: O(1)