2

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它，我在哪里做错了？

4

1 回答 1

2

对于某些固定的 α，我们选择的 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.
于 2021-01-29T20:38:04.313 回答