首页 > 试题广场 >

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

[单选题]
有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该算法的时间复杂度为（）(^符号是幂的意思) 
  • O(n^3)
  • O(nlogn)
  • O(n)
  • O(n^2)
查看答案及解析
添加回答
leozzy头像 leozzy

master 公式

T(N) = a*T(N/b) + O(N^d)

估计递归问题复杂度的通式，只要复杂度符合以下公式，都可以套用此公式计算时间复杂度

例子：递归方式查找数组最大值 T(N) = 2*T(N/2) + O(1)

T(N)：样本量为 N 的情况下，时间复杂度
N：父问题的样本量
a：子问题发生的次数（父问题被拆分成了几个子问题，不需要考虑递归调用，只考虑单层的父子关系）
b：被拆成子问题，子问题的样本量（子问题所需要处理的样本量），比如 N 被拆分成两半，所以子问题样本量为 N/2
O(N^d)：剩余操作的时间复杂度，除去调用子过程之外，剩下问题所需要的代价（常规操作则为 O(1)）

  1. log(b,a) > d -> 复杂度为O(N^log(b,a))
  2. log(b,a) = d -> 复杂度为O(N^d * logN)
  3. log(b,a) < d -> 复杂度为O(N^d)
发表于 2018-05-07 17:22:58 回复(0)
牛客9792607号头像 牛客9792607号
使用的是master公式，
T(N) = a*T(N/b) + O(N^d)
  1. log(b,a) > d -> 复杂度为O(N^log(b,a))
  2. log(b,a) = d -> 复杂度为O(N^d * logN)
  3. log(b,a) < d -> 复杂度为O(N^d)
发表于 2019-02-25 16:12:57 回复(0)
就想有个靠谱工作头像 就想有个靠谱工作
发表于 2018-04-02 16:18:25 回复(0)
提交观点

问题信息

爱奇艺 2018 Java工程师
来自：爱奇艺2018秋季校招...
上传者：小小
难度：
3条回答 5816浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号