Big Oh Notation - формальное определение

Question

Я сейчас читаю учебник для моего класса Java III. Мы читаем о Big-Oh, и меня немного смущает его формальное определение.

Формальное определение: «Функция f (n) имеет порядок не более g (n), то есть f (n) = O (g (n)), если существует положительное действительное число c и положительное целое число N такой, что f (n) <= cg (n) для всех n> = N. То есть cg (n) является верхней границей f (n), когда n достаточно велико. "

Хорошо, это имеет смысл. Но держись, продолжай читать ... книга дала мне такой пример:

"В сегменте 9.14 мы сказали, что алгоритм, который использует 5n + 3 операции является O (n). Теперь мы можем показать, что 5n + 3 = O (n), используя формальное определение Большой О.

Когда n> = 3, 5n + 3 <= 5n + n = 6n. Таким образом, если мы допустим f (n) = 5n + 3, g (n) = n, c = 6, N = 3, мы показали, что f (n) <= 6 г (n) для n> = 3 или 5n + 3 = На). Это если алгоритм требует времени, прямо пропорционального 5n + 3, это O (n). "

Хорошо, этот вид имеет смысл для меня. Они говорят, что если n = 3 или больше, 5n + 3 занимает меньше времени, чем если бы n было меньше 3 - таким образом, 5n + n = 6n - верно? Имеет смысл, поскольку если n было 2, 5n + 3 = 13, а 6n = 12, но когда n равно 3 или больше, 5n + 3 всегда будет меньше или равно 6n.

Вот где я запутался. Они дают мне другой пример:

Пример 2: «Покажем, что 4n ^ 2 + 50n - 10 = O (n ^ 2). Легко видеть, что: 4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n для любого n. Поскольку 50n <= 50n ^ 2 для n </p>

= 50, 4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2 для n> = 50. Таким образом, с c = 54 и N = 50 мы показали, что 4n ^ 2 + 50n - 10 = O (n ^ 2). "

Это утверждение не имеет смысла: 50n <= 50n ^ 2 для n> = 50.

Разве никто не собирается сделать 50n меньше, чем 50n ^ 2? Не больше или равно 50? Почему они даже упомянули, что 50n <= 50n ^ 2? Какое это имеет отношение к проблеме? </p>

Кроме того, 4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2 для n> = 50 будет истинным независимо от того, что n.

А как в мире сборочные цифры показывают, что f (n) = O (g (n))?

Answer 1

Имейте в виду, что вы ищете "верхнюю границу для f (n), когда n достаточно велико". Таким образом, если вы можете показать, что f (n) меньше или равно некоторому c g (n) для значений n, превышающих N, это означает, что c g (n) является верхней границей для f (n) и, следовательно, сложность f (n) O (g (n)).

Приведенные примеры предназначены для того, чтобы показать, что данная функция f (n) никогда не может выйти за пределы c * g (n) для любого n> N. Путем манипулирования начальной верхней границей, чтобы ее можно было выразить более просто (если 4n ^ 2 + 50n - это верхняя граница для f (n), то же самое относится и к 4n ^ 2 + 50n ^ 2, что равно 54n ^ 2, которое становится вашим 54 * g (n), где c = 54 и g (n) = n ^ 2), авторы могут показать, что f (n) ограничено c * g (n), что имеет сложность O (g (n)) и, следовательно, f (n).

Answer 2

Все, что касается выбора чисел, заключается в следующем: чтобы было проще. Поскольку вам разрешено выбирать любые числа, которые вам нравятся для N и c, автор просто выбирает что-то, где это легче всего увидеть. И это то, что вы также можете сделать (при написании экзамена и т. Д.).

Таким образом, хотя часто можно было бы использовать меньшее N, рассуждение становилось бы немного сложнее (часто требуя некоторых предыдущих знаний об анализе - мы все узнали годы назад, что x не растет так быстро, как х ^ 2 ... Но вы хотите записать доказательства анализа?)

Проще говоря, это сообщение :-) Поначалу немного странно привыкнуть к этому.

Answer 3

50n <= 50n^2 for n >= 50

потому что если n равно 50, то 50n - это то же самое, что и n ^ 2, потому что 50 * 50 равно 50 ^ 2.

Подставляя n^2 для 50n, получаем

* +1007 *

что очевидно.

Answer 4

Формальное определение:

• f (n) = O (g (n)) означает, что существуют c> 0 и n ₀ такие, что для любого n> = n ₀ f (n) < = c * g (n)
• f (n) = o (g (n)) означает, что для любого c> 0 существует n ₀ , такое что для любого n> = n ₀ f (n) <= c * g (n) </li>

Как вы можете заметить, они немного другие:)

Answer 5

Вероятно, причина того, что они сказали 50n <= 50n ^ 2 для n> = 50, заключается в том, что если n меньше 1, чем n ^ 2

Я понимаю, почему говорить 50n <= 50n ^ 2 для n> = 50 может показаться немного глупым. Но это все еще правда. В книге не сказано, что 50n <= 50n ^ 2 выполняется ТОЛЬКО для n> = 50; это было бы ложным.

В качестве аналогии, если я скажу "все мои братья и сестры говорят по-английски", это будет правдой, даже если есть много людей, говорящих по-английски, которые не являются моими братьями и сестрами.

Что касается доказательства, мы можем разделить его на разные утверждения.

 (1): 4n^2 + 50n - 10 <= 4n^2 + 50n  (for all n)
 (2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50)  
 (3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50)
 (4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50
 (5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54, 
           the statement  f(n) <= c g(n) for all n >= N is true
 (6): Therefore, by definition 4n^2 + 50n - 10=O(n^2). 

Должно быть ясно, что каждое из этих утверждений является верным, либо само по себе (1,2,3), либо в результате предыдущих утверждений.