首页 > 试题广场 >

有一个算法的递推关系式为:T(n) = 9 T(n 3)

[单选题]
有一个算法的递推关系式为:T(n) = 9 T(n / 3) + n,则该算法的时间复杂度为()(^符号是幂的意思)
  • O(n^3)
  • O(nlogn)
  • O(n)
  • O(n^2)
1.T(n) = 4*T(n/2) + n 则是第一种情况logba = 2,而n = n^1,所以1 < 2,所以为O( n^2 )

2. T(n) = 4*T(n/2) + n^2 则是第二种情况,注意此处的k=0的,又logba = 2,所以2 = 2,所以为O( n^2 * lgn )

3. T(n) = 4*T(n/2)+ n^3,则是第三情况,3 >2,所有结果是:O( f(n)) = O( n^3 )
发表于 2019-12-04 10:27:55 回复(0)