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

0

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

Пусть f{n)wg (п) — функции, которые преобразуют целые числа в реальные числа. Покажем, что/(п) есть Q(g(n)) (говорят, что/(п) есть большая омега g(n), если g(n) есть О (f (п)), то есть существует действительная константа с > 0 и целая константа щ > 1, такие, что/(п) > eg (п) для п > щ. Такое определение позволяет асимптотически утверждать, что одна функция больше или равна другой функции до постоянного множителя. Аналогично можно утверждать, что /(п) есть Q(g(ri)) (говорят, что «/(п) есть большая тета g (п)»), если/(п) есть 0(g (п)) и/(п) есть Q(g(n)), то есть существуют действительные константы с’ > 0 и с" > 0, а также целая константа по > 1, такие, что c’g(ri) < f(n) < c"g(n) для п > Такое определение позволяет утверждать, что две функции асимптотически равны до постоянного множителя. Ниже приводится несколько примеров подобных нотаций.

Пример 3.12: 3 log п + log log п есть Q(log п).

Доказательство: 3 log п + log log п > 3 log п для п > 2.

В примере показано, что элементы низшего порядка не являются определяющими при установлении нижнего предела в случае нотации большой омеги. Следующий пример показывает также, что элементы низшего порядка не являются определяющими и в случае большой 0.

Пример 3.13: 3 log п л- log log п есть ©(log п).

Доказательство: следует из примеров 3.13 и 3.18.

«Дальние родственники» большого О

Существует еще несколько способов асимптотически определить, является ли одна функция строго больше или строго меньше другой функции, используемых не так часто, как нотации большого О, большой Q или большой 0. Тем не менее, чтобы завершить данную тему, приводим их определения.

Пусть f(n) и g (п) — функции, которые преобразуют целые числа в реальные числа. Покажем, что/(п) есть o(g (п)) (говорят, что «/(п) есть малая og(n)»), если при любом значении константы с > 0 существует константа щ > 0, такая, что/(п) < cg(n) для п > щ. Аналогично можно утверждать, что/(п) есть со(g(n)) (говорят, что «/(п) есть малая омега g (я)»), если g(n) есть o(f(n)), то есть если при любом значении константы с > О существует константа щ > 0, так, что g (п) < cf (п) для п > щ. Интуитивно можно предположить, что о(.) асимптотически аналогична «меньше чем», а со(.) аналогична «больше чем».

Пример 3.14: функция f(ri) = 12п2 + 6п есть о{пъ) и со(п).

Доказательство: вначале покажем, что f(n) есть о(п3). Пусть с > 0 является константой. Если по = (12 +6)/с, то при п> по получим

Таким образом,/(л) есть о(пг).

Для того чтобы показать, что/(п) есть со(п), пусть с > 0 является константой. Если по = с/12, то при п> щ получим

Таким образом, /(п) есть со(п).

Если читатель знаком с понятием пределов, то можно отметить, что /(п) есть o(g (п)), если и только если

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

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

По теме:

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