T(n) = 7T(n/3) + n^2 和 T(n) = 7T(n/2) + n^2 的时间复杂度是多少 >>>>我同时应用了 akra-bazzi 和 master定理,但我得到不同的答案......
对于 T(n) = 7T(n/3) + n^2 使用 akra-bazzi 定理我得到 O(n^2) 并使用相同的定理 T(n) = 7T(n/2) + n^2 我再次得到 O(n^2) ,但在其他网络资源中,他们说使用大师定理会给出 O(n^log7) 。所以我对实际答案感到困惑。
根据主定理,
The solution to the recurrence relation,
T(n) = aT(n/b) + cn^k, where a ≥ 1, b ≥ 2 are integers,
and c and k are positive constants, satisfies
T(n) is
Θ(n^(log_b(a))) if a > b^k
Θ(n^k log(n)) if a = b^k
Θ(n^k) if a < b^k
因此,从那时起,
T(n) = 7T(n/2) + n^2
,然后是a = 7 ≥ 1
和b = 2 ≥ 1
。另外,对于 k = 2
,我们有 7 > 2^2 = 4
,因此 T(n)
是 Θ(n^(log_2(7)))
。根据大 theta 的定义,我们知道 T(n)
也是 O(n^(log_2(7)))
。