algorithm - 证明给定函数等于 o(N)

Question

我试图证明对于任何常量k，log^k N = o(N)(N 的小 O)

我所知道的一点点 o 是它遵循 T(n) = o(p(n)) 的形式，其中 T(n) 以 a 增长速率低于 p(n)。我也不能真正做一个限制并使用 L'hopital 规则 因为我不知道什么是 f(n) 或 g(n) 是。有人可以帮助我入门吗!

Answer 1

你需要证明这一点

    lim        (log^k N)/N  = 0
N -> infinity

写N = e^x , 就变成了

lim (x^k)/(e^x) = 0

现在，用指数函数的幂级数展开，

e^x = ∑ (x^n)/n!

获得该商的估计值。

剧透:用 n = k+1 选择术语给出 e^x > x^(k+1)/(k+1)!从中很容易得到 (x^k)/(e^x) < (k+1)!/x .