Proving Big O обозначение

Question

Доказательство 5n^2 + 2n -1 = O (n^2). Это то, что я пытался до сих пор:

5n^2 + 2n -1 <= 5n^2 + 2n^2 -n2 for n>1 
    5n^2+ 2n -1 <= 6n^2 for n>1 
    5n^2+ 2n -1 = O(n^2) [ c = 6n^2, n0 = 1 ] 

Это правильный способ доказать Big O нотации?

Answer 1

это выглядит нормально, я думаю, что если вы делаете это для своей работы по назначению или другой формальной работы, вы также можете сделать это более формальным способом, например, для выбора значения константы (c), например, f (n)/g (n). В противном случае это выглядит правильно.

Answer 2

Чтобы доказать, что ваше выражение O(n^2), вы должны показать, что она ограничена M*n^2 для некоторой постоянной M и некоторого минимального значения n. По инспекции, мы можем показать, что ваше выражение ограничено 10*n^2 для n=10:

Для n = 10:

5n^2 + 2n -1 <= 10*n^2 
500 + 20 - 1 <= 1000 
519 <= 1000 

Мы можем также показать, что выражение ограничено 10*n^2 для любого значения nбольше чем 10:

Для n > 10:

5n^2 + 2n -1 <= 10*n^2 
5*(10+i)^2 + 2*(10+i) -1  <= 10*(10+i)^2 
5*(i^2 + 20i + 100) + 2i + 19 <= 10*(i^2 + 20i + 100) 
2i + 19 <= 5*(i^2 + 20i + 100) 
2i + 19 <= 5i^2 + 100i + 500 
5i^2 + 98i + 481 >= 0, which is true for `i > 0` 

Вот ссылка на статью Википедии о Big-O нотации:

https://en.m.wikipedia.org/wiki/Big_O_notation

Update:

Обратите внимание, что на практике для того, чтобы обозначить ваше выражение O(n^2) мы выиграли» Прибегать к таким уродливым письменным доказательствам. Вместо этого мы просто узнаем, что термин n^2 будет доминировать над выражением для больших n и что общее поведение будет O(n^2). И ваше выражение также O(n^3) (и O(n^4) и т. Д.).

Answer 3

Мы F (п) = 5 * п^2 + 2 * п-1 и г (п) = п^2

Для того чтобы доказать п (п) = О (г (п)), нам просто нужно найти 2 константы, а именно c> 0 и n_0, st f (n) < = c.g (n) для всех n> = n0.

Выберем некоторое значение c = 5.5. Оценим и построим f (n) и c * g (n). Как мы можем видеть из графика, и теоретически можно показать его, так как n^2/2 - 2 * n + 1 = (n^2-4 * n + 2)/2 = ((n-2)^2- 2)/2> = 0 для всех п> = 4, из этого следует, что 5 * п^2 + 2 * п-1 < = 5.5 * п^2 для всех п> = п0 = 4. Следовательно, f (n) = O (g (n)). (Доказанные)