algorithm - T(n) = T(n/2) + clog(n) = O(log(n)^2) 的归纳证明

Question

log() = log base 2 of ()
log()^2 = log^2 base 2 of ()

我被这个归纳证明所困扰。我有以下递归关系

T(n) = T(n/2) + Theta(log(n))

我必须证明T(n) = O(log(n)^2)

使常量显式化:

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

我知道对于 O 的定义我必须找到 k > 0和n' > 0这样t(n) <= k(log(n)^2)对于每个 n >= n'

T(n) = O(log(n)^2)假设对每个 m < n 都是如此我有那个t(m) <= k(log(m)^2)是真的:

给定
T(n) <= k(n/2)(log(n/2)^2) + c log(n) =
= k(n/2)(log(n)^2 - 1) + c log(n)
= k(n/2)(log(n)^2)) - kn/2 + c log(n) .

所以

k(n/2)(log(n)^2) - kn/2 + c log(n) <=? k(log(n)^2) <---这就是我被困住的地方

我找不到任何k也不n这将使这个工作正常，我在哪里做错了？

Answer 1

对于我们选择的一些固定的 α, M > 0，T(n) ≤ α (log(n) + 1) log(n) + M 就足够了，因为这个函数是 O(log(n) ²)。您没有给我们一个基本情况，所以我们假设这对于足够小的 n 成立(不失一般性，根据需要设置 M)。

归纳步骤表明 T(n/2) ≤ α (log(n/2) + 1) log(n/2) + M 意味着 T(n) ≤ α (log(n) + 1) log(n) + M。我们有

T(n)
= T(n/2) + c log(n)
≤ α (log(n/2) + 1) log(n/2) + M + c log(n)
= α log(n) (log(n) − 1) + M + c log(n).

如果我们设置 α = c/2，那么

T(n)
≤ α log(n) (log(n) − 1) + M + 2 α log(n).
= α (log(n) + 1) log(n) + M.