algorithm - 难以理解 little-o 符号示例

Question

我遇到了这个问题

9n <= cn^3

基本上我可以开始

9/c <= n^2

但是我该如何解决其余的问题？

Answer 1

little o是的 定义

我们说f(x)=o(g(x))。

让 f(x)=9*x 和 g(x)=c*x^3 其中 c 是一个正常数。当 x 趋于无穷大时，f(x)/g(x) 趋于 0。所以我们可以说f(x)=o(g(x)).

渐近符号适用于足够大的 n.so 对于较大的 n 值

9n << cn^3

对于所有 c>0。

Answer 2

阅读此链接以了解 big-O 和 little-O链接

看看你的方程，当 n=3 时，它变成 9*3=23=3^3，所以对于 n<3 9n > n^3。因此，如果您选择 c 作为任何数字以使 n<3 时 9n<=n^3，那么它可以在 O(n) 中。