Асимтотический анализ

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

Рассмотрим задачу поиска некоторого элемента в отсортированном массиве. Простейший способ поиска - это линейный поиск, который просматривает весь массив в поисках искомого элемента. Данный алгоритм имеет линейный порядок роста.

Второй способ найти искомый элемент - это бинарный поиск, который использует тот факт, что массив уже отсортирован. Данный алгоритм имеет логарифмический порядок роста.

Чтобы понять как асимтотический анализ решает вышеуказанные проблемы при анализе алгоритмов мы запустим линейный алгоритм поиска на быстром компьютере, а бинарный алгоритм на медленном компьютере.

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

Таким образом, машино зависимые константы всегда могут быть проигнорированы после определенных значений размера входных данных.

Нужно понимать, что асимтотический анализ не является совершенным средством для анализа алгоритмов, но это лучший способ на текущий день. Например, алгоритм быстрой и пирамидальной сортировки имееют одинаковый порядок роста в завимисомти от размера входных данных ($$n \log n$$). Однако константы скрытые за порядком роста достаточно различаются. Несмотря, на то, что оба алгоритма совпадают чисто асимтотически, время работы быстрой сортировки оказывается значительно меньше времени работы пирамидальной сортировки. Так, с точки зрения асимтотического анализа, мы не можем судить, какой из этих алгоритмов сортировки лучше, так как мы игнорируем константные множители.

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

Недостатки асимптотического анализа

На практике, помимо асимтотического анализа существуют некоторые соображения которые имеют важное значение при выборе между алгоритмами. Иногда, алгоритм с худшей асимптотикой является предпочтительнее. Пусть алгоритм А асимптотически лучше алгоритма В. Вот некоторые общие проблемы с алгоритмами, которые имеют лучшую асимптотику:

• Сложность реализации: алгоритмы с лучшей сложностью часто являются (гораздо) более сложным. Это может увеличить время кодирования и константы.

• Малые размеры входных данных: Асимптотический анализ игнорирует малые размеры входных. При малых размерах входных, постоянные константы или слагаемые с более низким порядком могут доминировать время работы алгоритма, в результате чего алгоритм B будет работать быстрее алгоритма A.

• Худшем случай и средний случай: Если А имеет более лучшие показатели в худшем случае, чем B, но средняя производительность B с учетом ожидаемого ввода лучше, то B может быть лучшим выбором, чем А. И наоборот, если худший случай алгоритма B неприемлем (скажем, опасным для жизни или критически важных причин), тогда должен использоваться алгоритм А.

МУСОР

Асимптотическое поведение функции $$f(n)$$ (например, $$f(n) = cn, \, f(n)=cn^2$$ и т.д.) относится к росту $$f(n)$$ когда $$n$$ становится большим. Как правило, мы игнорируем малые значения $$n$$, так как, как правило мы, заинтересованы в оценке, насколько программа будет медленной на больших входных данных. Хорошее правило: чем медленнее асимптотическая скорость роста, тем лучше алгоритм.

По этому показателю, линейный алгоритм ($$f(n) = d \cdot n + k$$) всегда асимптотически лучше, чем квадратичный ($$f(n) = c \cdot n^2 + q$$). Это происходит потому, что для любого заданного (положительного) c,k,d, иq всегда есть некоторое значение $$n$$, при котором величина $$с \cdot n^2 + q$$ обгоняет $$d \cdot n + k$$. При небольших значениях $$n$$, квадратичный алгоритм вполне может занять меньше времени, чем линейный, например, если $$c$$ значительно меньше, чем $$d$$ и/или $$k$$ значительно меньше $$q$$. Тем не менее, линейный алгоритм всегда будет лучше для достаточно больших входных значениях $$n$$.