求解T(n)<T(7n/10)+kn+b

求解T(n)<T(7n/10)+kn+b的时间复杂度,k>0.
这题答案是O(n),但是我求不出来。

阅读 3.1k
1 个回答

a = 1, b = 10/7, logba = 0
f(n) = n1 where 1 > logba = 0

7n/10 <= kn, k = 7/10
所以用master theorem case 3,
T(n) = Θ(n)

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题