algorithm - 分治法的时间复杂度

Question

我有找到复杂性的主定理，但问题是主定理说

对于形式的重复

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

有以下三种情况： /******************logba 表示 a 以 b 为底的 log ******************/

1. If f(n) = Θ(n^c) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(n^c) where c = Logba then T(n) = Θ(ncLog n)

3. If f(n) = Θ(n^c) where c > Logba then T(n) = Θ(f(n))

现在解决我的问题

T(n) = T(n/2) + n^2

我的解决方案和c = 2with as So 在这种情况下它会下降，复杂性是什么logba = log21base = infinity

Answer 1

在你的情况下b=2，a=1所以Log_b(a)是log of 1 in base 2而不是log of 2 in base 1。

看：

T(n) = aT(n/b) + f(n)
T(n) =  T(n/2) + n^2

因为Log_b(a) = Log_2(1) = 0，您属于第 3种情况。