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.