大O/大Oh符号问题

Question

我正在学习大O符号，但是我对这道题的解法有困惑：

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。请有人给我解释一下吗？

- Mus

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 成为最合理 / 自然的解决方案。

- Ishtar

Answer 2

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

要在您的情况下验证这一点：如果 n >= 10，那么：

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

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

请注意，其他c和n0的值也可以使用；您只需要找到一对即可。

- Simon Nickerson

---

非常感谢您的回答，但我仍然不太理解这个问题（或者说大O符号）。您知道有哪些有用的资源可以参考吗？关于“选择c = 3和n0 = 10”-这是在要求我使用这些值并尝试解决2n + 10 ≡ O(n)的问题吗？还是我误解了？感谢您的时间。 - Mus

请参考@Ishtar的答案，他从另一个角度来解决这个问题。 - Simon Nickerson

Answer 3

let f(n) = 2n+10
as per the Big-Oh notation,
f(n)<= c*g(n)  ----->eq1(let)
2n+10 <= 2n+n  
2n+10 <= 3n     for n>=10 //here the constant 10  is replaced by n ---->eq2

比较方程式eq1和eq2 c=3以及g(n)=n，当n=10时的值

f(n)= O(g(n)) = O(n)

- Pitta Maheswari

---

你的回答可以通过添加额外的支持信息来改进。请[编辑]以添加更多详细信息，例如引用或文档，以便其他人可以确认您的答案是否正确。您可以在帮助中心找到有关如何撰写良好答案的更多信息。 - Community

Answer 4

在大O符号中，您会忽略加和乘的数字，并使用最大的幂次。

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

- Reza