Big-O/Big-Oh表示法问题

Question

我正在复习Big- over符号，我在理解这个问题的解决方案时遇到了一个问题：

Is 2n + 10 ≡ O(n)?
Can we find c and n0?

2n + 10 <= cn
(c-2)n >= 10
n >= 10/(c-2)

Pick c = 3 and n0 = 10

在此示例中还使用了一个图：

​

​

我对c=3和n0 = 10感到困惑。有没有人能开导我一下？

Answer 1

我会以不同的方式解决2n + 10 <= cn问题。

2n + 10 <= cn
2 + 10/n <= c //divide by n
c >= 2 + 10/n

显然c必须大于2。现在取你最喜欢的大于2的数字。c=2.718。这给了我们

2n + 10 <= 2.718*n
10 <= 0.718*n //subtract 2n
13.93 <= n

因此，2n + 10 <= c*n。如果我们把c=2.718和n比15更大。(15是因为它大于限制，13.93，我喜欢15。)

任何大于2的c都可以，c=100000000000000000000000也可以(但是写下来需要大量的墨水和纸张)。

使用c=3可能会更容易一些。这将会给你

2n + 10 <= 3*n
10 <= n //subtract 2n

这使得3成为最符合逻辑/最自然的解决方案。

Answer 2

说一个函数f(n)是O(n)，意味着你可以找到c和n0，这样对于所有的n >= n0，f(n) <= cn。

要在您的案例中验证这一点: if n >= 10，则：

f(n) =  2n + 10
     <= 3n         // because 10 <= n
     = cn

所以对于所有的n >= 10都是f(n) <= cn，所以f(n)是一个O(n)函数。

注意，c和n0的其他值也是有效的；您只需要找到一对。

Answer 3

在Big-O表示法中，您省略了加法和乘法。同时也使用了最大的能量。

10*N^3+ 23*N^2 + 43*N + 154 = O(N^3)