T(n) = 7T(n/2) + n^2 和 T(n) = 7T(n/3) + n^2 的时间复杂度

Question

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) 。所以我对实际答案感到困惑。

Answer 1

根据主定理，

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)))

。