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

Question

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

我对小 o 所知道的只是它遵循以低于T(n) = o(p(n))的T(n)速度增长的形式p(n)。我也不能真正做一个限制和使用L'hopital rule，因为我不知道是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。