math - 从第一原理证明 little-O

Question

证明 f(n) = 2010n^2 + 1388n 属于 o(n^3)

Little-O 定义

到目前为止我的工作：这一定是真的：对于所有常量 c>0，存在一个常量 n0>0 使得所有 n>n0 的 0<=2010n^2 + 1388n<=cn^3

通过简化我们得到： c>= 2010/n + 1388/n^2

不知道接下来要做什么才能找到 n0。

Answer 1

使用little-o 符号的等效定义可能会更轻松：我们说 f = o(g) if

lim _{n → ∞} f(n) / g(n) = 0

在您的情况下，这意味着您将证明

lim _{n → ∞} (2010n ² + 1388n) / n ³ = 0

要看到这一点，请注意

lim _{n → ∞} (2010n ² + 1388n) / n ³

= lim _{n → ∞} (2010n ² / n ³ ) + (1388n) / n ³

= lim _{n → ∞} (2010 / n) + (1388 / n ² )

= lim _{n → ∞} (2010 / n) + lim _{n → ∞} (1388 / n ² )

= 0 + 0

= 0

希望这可以帮助！