Вычислительная сложность алгоритмов

↑

▷ Содержание

⇐ ПредыдущаяСтр 33 из 43Следующая ⇒

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

O(f(N)) служит для обозначения множества всех функций g(N) таких, что существуют положительные константы С и N₀, для которых  при всех .

o(f(N)) служит для обозначения множества всех функций g(N) таких, что для всех положительных констант С сущест­вует некое No, при котором g(N) Cf(N) для всех  (или, что то же самое, ).

Пример:

Рассмотрим эти оценки на примере бинарного поиска на отсортированном массиве чисел. Пусть в массиве N элементов. Поиск осуществляется следующим образом:

массив a₁ a₂ … a_N искомый элемент x

Поиск идет на 1 ... N элементах. Сравниваем x и a_[N/2] . Возможные результаты:

1. x = a_[N/2] поиск завершен.

2. x < a_[N/2] продолжаем поиск на 1 .. [N/2] элементах

3. x > a_[N/2] продолжаем поиск на [N/2].. N элементах

Таким образом в худшем случае поиск закончится когда будет производиться на множестве из двух элементов a_i a_i+1 . На i – м шаге количество рассматриваемых элементов равно . Поиск закончится если 2ⁱ N.

Итак время работы алгоритма можно оценить как O(log₂N) = O(ln N)

Несомненно, пространственная (объем используемой памяти) и времен­ная сложности как функции от размеров задачи являются дву­мя фундаментальными оценками эффективности при анализе алгоритмов.

Чаще всего при описании алгоритмов будет приводиться оценка их сложности для худшего случая. Сложность для худшего случая — это максимальная мера эффективности данного алгоритма для всех задач данного размера, и ее нельзя путать со сложностью в среднем (или ожидаемой), которая отличается тем, что дает оценку наблюдаемого поведения этого алгоритма. К сожалению, анализ поведения в среднем значительно более сложная вещь, чем анализ худшего случая, по двум причинам: во-первых, существенные математические трудности возникают, даже если удачно выбрано исходное распределение; во-вторых, часто с трудом достигается согласие в том, что именно выбранное распределение является реальной моделью изучаемой ситуации.

Еще один важный момент, который следует отметить, связан с тем, что обозначения «порядка» скрывают мультипликативные константы. Следовательно, оценка сложности достигает своей законной силы только при весьма больших размерах задачи; именно поэтому такой подход называется асимптотическим анализом. Следовательно, вполне вероятно,— и действительно часто бывает так, — что при малых размерах задачи наиболее пригоден алгоритм, который асимптотически не оптимален. Это предостережение никак нельзя игнорировать при выборе алго­ритма для конкретного приложения.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману