o符号示例

2018-06-14 00:08:58

我遇到了这个问题

9n <= cn^3

基本上我可以深入

9/c <= n^2

但我如何解决其余问题？

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的大值，使用渐近符号可以得到足够大的n.so值

9n << cn^3

对于所有c> 0。

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

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

你只需要证明对每一个c都有一个n0 ，使得对于所有的n > n0 ： 9n <= n^3 。通过只解出这个方程到n你会得到（假设n正数）：

n >= 3/sqrt(c)

现在取n0 = 3/sqrt(c) ，其存在并且对于所有c > 0是正的，则对于所有n > n_0进行反向计算：

cn^3-9n = n*(cn^2-9)
        = n*c*(n^2-9/c)
        = n*c*(n-3/sqrt(c))*(n+3/sqrt(c))
        = n*c*(n-n0)*(n+n0)
        > 0

（因为n>n0>0 ， c>0 ， n>n0且n>n0>-n0 ）

因此

9n < cn^3

这意味着9n in o(n^3)中的9n in o(n^3) 。

链接地址: http://www.djcxy.com/p/39887.html