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

问题描述

问 题

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

解决方案

a = 1, b = 10/7, log_ba = 0
f(n) = n¹ where 1 > log_ba = 0

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

这篇关于c++ - 求解T(n)&lt;T(7n/10)+kn+b的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！