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

0

Считается дурным тоном говорить, что «/(я) < 0(g (я))», так как определение нотации большого О уже содержит «меньше или равно». В то же время, несмотря на распространенное употребление, не вполне корректно записать «/(я) = 0(g(n))» (в обычном понимании отношений, обозначенных символом «=»), и совершенно не верно, что «/(я) > 0(g(n))», или «/(Л) > 0(g(n))». Оптимальным выходом будет определение «/(я) есть 0(g(n))». Либо, используя математические символы, данное отношение можно выразить следующим образом:

так как нотация большого О обозначает целое множество функций.

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

Такая запись означает, что существуют две константы с > 0 и щ > 1, причем j{ri) < g(n) + ch(ri) при п > щ. В самом деле, иногда может возникнуть необходимость определения главного члена асимптотической характеристики, в таком случае можно сказать, что «/(я) есть g(n) + 0(h(n))», причем h(n) растет медленнее, чем g(n). Например, можно определить, что 2п log п + 4п + Юл/я есть 2я log я + О(я).

Выскажем некоторые предостережения в отношении использования асимптотических нотаций. Во-первых, следует отметить, что нотация большого О и аналогичные ей могут привести к ошибочным результатам, если «скрываемые» ими постоянные множители достаточно велики. Например, хотя функция 10,00я есть 0(я), если она обозначает время выполнения алгоритма, сравниваемого с алгоритмом, время выполнения которого равно \0n\ogn, следует выбрать алгоритм со временем Q(nlogn), даже несмотря на то, что асимптотически время выполнения, выраженное линейной функцией, меньше. Данный выбор обусловлен тем, что постоянный множитель Ю100, называемый «hiding», считается верхним пределом числа атомов в наблюдаемой части вселенной. Таким образом, маловероятно, что алгоритму придется решать задачу реального мира с таким размером исходных данных. Таким образом, при использовании нотации большого О следует обращать внимание на постоянные множители и элементы низшего порядка, которые могут «скрываться» за ними.

Сделанное выше замечание вынуждает обратиться к вопросу о том, что же есть «быстрый» алгоритм. В целом любой алгоритм, время выполнения которого 0(п log я) (при условии приемлемого постоянного множителя) можно считать эффективным. Даже метод со временем 0(п2) может при определенных условиях быть достаточно быстрым, например, в случае малого значения п. Однако время выполнения алгоритма, равное 0(я2), не может считаться эффективным ни при каких условиях.

Известна история об изобретателе шахмат. Этот мудрец попросил своего царя в качестве оплаты за услугу, чтобы тот положил на 1 клетку доски 1 зерно риса, на вторую — 2 зерна, на третью — 4 зерна, на четвертую — 8, и так далее. Хорошим средством проверки навыков программирования является задание написать программу для подсчета точного числа рисовых зерен, которое должен был бы заплатить царь. В действительности, если Java-nporpaMMa будет написана для вычисления полученного значения в виде целого числа, это приведет к ошибке переполнения целых чисел (хотя исполняющая машина может и не выдать подобного сообщения об ошибке). Для того чтобы представить полученное значение, потребуется использование класса Biglnteger.

Эффективные и неэффективные алгоритмы можно различать по следующему признаку: выражено ли время их выполнения полиномиальной или показательной функцией. То есть одни алгоритмы можно отнести к группе, время выполнения которых равно 0(пк), где константа к > 1, а другие — к группе, время выполнения алгоритмов которой 0(с"), где константа с > 1. Как и ко всем прочим понятиям, рассмотренным в данном разделе, к использованию приведенных рекомендаций следует также подходить взвешенно, так как вряд ли можно считать алгоритм со временем выполнения 0(я100) «эффективным». Тем не менее разделение алгоритмов на полиномиальные и показательные считается надежным средством определения их эффективности.

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

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

По теме:

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