math - 数据结构 - 运行时和渐近界

Question

如果 a>0 是一个固定变量，则证明：lg(n+a) = Θ(lg n)

请指教。

Answer 1

为了证明 f(n) = Θ(g(n))，你需要证明存在一个非零 k 使得

lim (n → ∞) f(n) / g(n) = k

在你的情况下，我们想证明

lim (n → ∞) lg(n + a) / (lg n)

这是 ∞ / ∞ 类型的不确定形式，因此我们可以应用l'Hôpital 规则并取分子和分母的导数得到

lim (n → ∞) lg(n + a) / (lg n) =

lim (n → ∞) (1 / n + a) / (1 / n) =

lim (n → ∞) n / (n + a)

这又是一个不确定的形式，所以应用 l'Hôpital 的规则给出

lim (n → ∞) n / (n + a)

= lim (n → ∞) 1 / 1

= 1

因此，存在一个非零常数（即 1），使得 lg(n + a) / lg n 当 n 趋于无穷时的极限等于该常数，因此 lg(n + a) = Θ(lg n)。

希望这可以帮助！