Big-O/Big-Oh 符号问题

Question

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

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