分而治之的时间复杂度

Question

我有求复杂性的主定理但是 问题是 主定理说

表格的重复

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

有以下三种情况： /******************logba 表示 a 以 b 为基数的日志 **************/

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 = 2 和 logba = log 的 2 与 1 作为 base = 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.