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

[单选题]

有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该算法的时间复杂度为（）(^符号是幂的意思)

```
O(n^3)
```
```
O(nlogn)
```
```
O(n)
```
```
O(n^2)
```

查看正确选项

PrConstantin

http://blog.csdn.net/shanshanpt/article/details/8696955

发表于 2017-11-30 17:07:31 回复(0)

littleZzz

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)