Главная » Java, Структуры данных и алгоритмы » Нотация большого О

0

Пусть f(n)ng (п) являются функциями, которые преобразуют неотрицательные целые числа в действительные. Докажем, что/(п) есть 0(g (п)), если существует действительная константа с > 0 и целочисленная константа по > 1, такие, что/(п) < eg (п) для любого целого числа п > щ. Такое определение функции зачастую называется нотацией большого О, так как иногда говорят, что f(n) является большим О функции g(n). Другими словами, можно сказать, что/(п) есть порядковая функция g(n) (определение показано на рис. 3.4).

Пример 3.6: In – 2 есть О(п).

Доказательство: по определению нотации большого О необходимо найти действительную константу с > 0, а также целочисленную константу по > I, так, что In -2 щ < сп для любого целого числа,я > щ. Одним из очевидных вариантов является с = 7, а щ = 1. Безусловно, это один из бесконечного множества вариантов; с в данном случае может принимать значение любого действительного числа, равного или большего 7, а щ — любое целочисленное значение, большее или равное 1.

позволяет выразить, что функция п «меньше или равна» другой функции (в определении это выражается знаком «<») до определенного постоянного значения (константа с в определении) и по мере того, как п стремится к бесконечности (условие «п > щ» в определении).

Зачастую нотация большого О используется для характеристики времени выполнения и использования памяти на основании некоего параметра п, который может различаться в конкретных ситуациях, однако, как правило, зависит от целей анализа. Например, если требуется найти

Рис. 3.4. Наглядное изображение нотации большого О. Функция f(n) есть 0(g(n)), так как /(п) < eg(п) при п > л0

наибольший элемент массива целых чисел (см. аггауМах, представленный во фрагментах кодов 3.1 и 3.2), то вполне естественно использовать п для обозначения числа элементов массива. позволяет не учитывать постоянные множители и частные детали, а сосредоточиться только на основных компонентах функции, определяющих ее возрастание.

Используя нотацию большого О, можно представить математически точное определение времени выполнения алгоритма аггауМах (см. фрагменты кодов 3.1 и 3.2) независимо от применяемых аппаратного и программного обеспечения.

Утверждение 3.5. Время выполнения алгоритма аггауМах, определяющего максимальный элемент массива целых чисел, есть функция О(п).

Доказательство. Как было отмечено в п. 3.5.1, максимальное число простейших операций, выполняемых алгоритмом аггауМах, равно 7 л – 2. Таким образом, существует положительная константа а, которая определяется единицами измерения времени, а также применяемым при реализации, компиляции и исполнении аппаратным и программным обеспечениями, при которой время выполнения алгоритма аггауМах для размера исходных данных л равно максимально я(7л-2). Используя нотацию большого О для с = 7а, ъпо = 1, можно сделать вывод, что время выполнения алгоритма аггауМах является О(п).

Рассмотрим еще несколько примеров, демонстрирующих использование нотации большого О.

Пример 3.7: 20л3 + 10л log л + 5 есть 0(л3).

Доказательство: 20л3 + Юл log л + 5 < З5л3 для л > 1.

В сущности, любой многочлен (полином) акпк + ак_1пк~{ + …+ я0 является 0(пк).

Пример 3.8: 3 log л + log log л есть 0(log л).

Доказательство: 3 log л + log log л < 4 log л для л > 2. Следует отметить, что log log л не определен для л = 1. Поэтому используем л > 2.

Пример 3.9: 2,0° есть 0(1).

Доказательство: 2100 < 2100 • 1 для л > 1. Заметьте, что переменная л не присутствует в неравенстве, так как в данном случае рассматриваются постоянные функции.

Пример 3.10: 5 / л есть 0(1 / л).

Доказательство: 5 / л < 5(1 / л) для л > 1 (на самом деле это убывающая функция).

В целом можно сказать, что нотация большого О используется для максимально точного описания функции. Если верно, что функция /(п) = 4пг + 3л4/3 есть О(я^) или даже 0(пъ log п), то более точно будет сказать, что/(п) есть 0(пг). Рассмотрим следующую аналогию. Голодный путешественник долго едет по пустынной проселочной дороге и встречает местного фермера, который возвращается домой с рынка. Если путешественник спросит фермера, сколько ему нужно ехать, чтобы добраться до ближайшего места, где он может поесть, фермер может вполне правдиво ответить: «Не более 12 часов», но более точным (и полезным) будет, если он скажет: «Всего в нескольких минутах езды отсюда находится рынок». Таким образом, даже используя нотацию большого О, следует стремиться сообщать все возможные подробности.

Утверждение 3.6: пусть d(n), e(ri),f(ri) и g(n) являются функциями, которые преобразуют неотрицательные целые числа в неотрицательные действительные числа. Тогда

1.       Если d (п) есть О (/(п)), то ad(ri) есть О (f(n)) для любой константы

в > о.

2.       Если d (п) есть 0(f(n)) и е (п) есть 0(g(n), то d(ri) + e{ri) есть

О (/(л)+[11](*))?

3.       Если d (п) есть 0(f(n)) и е (п) есть 0(g(n), то d (п) е (п) есть 0(f(n)g(n)).

4.       Если d (п) есть 0(f (п)) и /(п) есть О (g (п), то d (п) есть О (g (п)).

5.       Если/(п) является многочленом степени d (то есть f(ri) = + а\п + + … + adnd), то f(n) есть 0(nd).

6.       пх есть О (а") для любого целого х > 0 и а > 1.

7.       log я* есть О (log п) для любого целого х > 0.

8.       log* п есть О (пу) для любой целой константы х > 0 и у > 0.

Считается дурным тоном включать в нотации большого О постоянные множители и члены низшего порядка. Например, не следует говорить, что функция 2п2 есть О (4п2 + 6п log п), хотя это выражение абсолютно верно. Функцию большого О следует описывать самым простым способом.

Пример 3.11: 2пг + 4п2 logлг есть 0(пг).

Доказательство: для доказательства используем правила из утверждения 3.16:

При анализе алгоритмов и структур данных часто применяются некоторые функции, имеющие особые названия. Например, термин «линейная функция» обозначает функции вида О(п). В табл. 3.1 представлены функции, часто используемые при анализе алгоритмов.

Логарифмическая

Линейная

Квадратичная

Полиномиальная

Показательная

0(\ogri)

0{п)

0(пг)

0(nk)(k > 1)

0{а")(а > 1)

Таблица 3.1. Классы функций

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии