Проблема обозначений 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

В этом примере также используется график:

Я не понимаю, как с = 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.)

Любое c больше, чем 2 работает, 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.

Чтобы убедиться в этом в вашем случае: если n> = 10, то:

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

То есть f(n) <= cn для всех n >= 10, поэтому f(n) является функцией O(n).

Обратите внимание, что другие значения для c и n0 работают; вам просто нужно найти одну пару.

Answer 3

В записи Big-O вы отбрасываете числа, добавленные и умноженные. А также используйте самую большую мощность.

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