Большой, О, Нотация - формальное определение
Я читаю учебник прямо сейчас для моего Java III классов. Мы читаем о Большом О, и я немного смущен его формальным определением.
Формальное Определение: "Функция f (n) имеет порядок в большей части g (n) - то есть, f (n) = O (g (n)) - если положительное вещественное число c и положительное целое число N существуют таким образом что f (n) <= c g (n) для всего n> = N. Таким образом, c g (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 = O (n). Таким образом, если алгоритм требует времени, прямо пропорционального к 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
= 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.
Разве какой-либо n не собирается делать 50n меньше, чем 50n^2? Не просто больше, чем или равный 50? Почему они даже упоминали что 50n <= 50n^2? Что это имеет отношение к проблеме?
Кроме того, 4n^2 + 50n - 10 <= 4n^2 + 50n^2 = 54n^2 для n> = 50 будет верным, каков n.
И как в мире числа выбора показывает что f (n) = O (g (n))?
5 ответов
Имейте в виду, что вы ищете «верхнюю границу 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).
Вся суть подбора чисел заключается в следующем: Чтобы было проще. Поскольку для N и c можно выбирать любые числа, которые вам нравятся, автор просто выбирает что-то, где это легче всего увидеть. И это то, что вы также можете сделать (при написании экзамена и т.д.).
Поэтому, хотя часто можно использовать меньшее N, рассуждения становятся немного сложнее (часто требуя некоторых предыдущих знаний об анализе - мы все узнали много лет назад, что x не растет так быстро, как x^2... Но хотите ли вы записывать доказательство анализа?)
Keep it simple, is the message :-) Просто поначалу немного непривычно к этому привыкать.
50n <= 50n^2 for n >= 50
потому что если n равно 50, то 50n равно n^2, так как 50*50 равно 50^2.
Подставляя n^2 в 50n, получаем
n^2 <= 50n^2 for n >= 50
что очевидно.
Формальное определение:
- f (n) = O (g (n)) означает, что существуют c> 0 и n 0 такие, что для любого n> = n 0 f (n) <= c * g (n)
- f (n) = o (g (n)) означает, что для любого c> 0 существует n 0 такое, что для любого n> = n 0 f (n) <= c * g (n)
Как вы можете заметить, они немного отличаются :)
Вероятно, причина, по которой они сказали 50n<=50n^2 для n>=50, заключается в том, что если n меньше 1, то n^2 < n. Конечно, если n является положительным целым числом, то да 50n<=50n^2. В этом случае кажется, что n предполагается положительным целым числом, хотя формальное определение, которое они дают, не указывает на это явно.
Я понимаю, почему говорить 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), либо в результате предыдущих утверждений.