Big-O/Big-Oh表示法问题 [英] Big-O/Big-Oh Notation Problem

问题描述

我正在处理Big-Oh表示法，但在理解该问题的解决方案时遇到了问题:

I am going over the Big-Oh notation, and I have a problem understanding the solution to this question:

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

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

There is also a graph used in this example:

我对c = 3和n0 = 10感到困惑.有人可以启发我吗?

I am confused as to how c = 3 and how n0 = 10? Can somebody please enlighten me?

推荐答案

我将以不同的方式解决 2n + 10< = cn .

I would solve 2n + 10 <= cn differently.

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

显然 c 必须大于2.现在将您喜欢的数字大于2.嗯. c = 2.718 .这给出了

Clearly c has to be bigger than 2. Now take your favorite number bigger than 2. Uhm. c=2.718. This gives

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.).

Thus, 2n + 10 <= c*n. If we take c=2.718 and n bigger than 15. (15 because it's bigger than the limit, 13.93, and I like 15.)

任何大于2的c都起作用，c = 100000000000000000000000也可以(但是，写下来要花很多墨水和纸张.)

Any c bigger than 2 works, c=100000000000000000000000 is fine too (but, it costs much ink and paper to write down.)

采用 c = 3 可能更容易.那会给

It might have been easier to take c=3. That would give

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

这使3是最合乎逻辑/最自然的解决方案.

This makes 3 the most logical / natural solution.

这篇关于Big-O/Big-Oh表示法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！