Вычисление асимптотической сложности алгоритма Часть I. Основные понятия.

Недавно в нашем паблике была опубликована статья в которой мы познакомились с первым алгоритмом сортировки — пузырьковой сортировкой, так же было выпущено еще несколько статей с алгоритмами такими как, например решето Эратосфена и алгоритм кэширования. В статье о пузырьковой сортировке мы затронули такое понятие как асимптотическая сложность алгоритма и дали ей неформальное определение — количество операций, выполняемых алгоритмом в худшем случае. В этот раз мы дадим более точное определение и разберем наиболее частые виды асимптотической сложности, а во второй части, которая выйдет завтра познакомимся с правилами ее вычисления.

Итак, для начала дадим определение:

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

Например O(N?) (как в случае с алгоритмом пузырьковой сортировки) означает, что по мере увеличения количества входных данных время работы алгоритма (во многих случаях и памяти, хотя для памяти, как правило сложность вычисляется отдельно) возрастает квадратично. Если дать такому алгоритму на вход в 2 раза больше данных, то время его работы возрастет в 4 раза.

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

1. O(1)

Алгоритм с такой производительностью выполняется за один и тот же промежуток времени, как правило это какая то одна команда, ведь за 1 операцию мы не можем даже просмотреть входные данные. Примером алгоритмов выполняющихся за O(1) могут служить арифметические операции, операции присваивания, сравнения, логических действий, доступ к элементам массива по индексу, чтение верхнего элемента стека, очереди, и т.д.

2. O(log(N))

У алгоритма с логарифмической производительностью количество рассматриваемых элементов делится на какое то константное значение (чаще всего 2) с каждой итерацией. Логарифмическое время является очень быстрым, так как даже при 50-значном N алгоритму придется сделать чуть больше 100 (если основание логарифма равно 2) итераций. Примерами алгоритмов работающих за логарифм служат: бинарный и тернарный поиски, поиск элемента в бинарном древе.

3. O(sqrt((N))

sqrt(N) — функция извлечения квадратного корня. Эта функция так же возрастает довольно медленно и для многих алгоритмов sqrt(N) — отличное время. В качестве примеров можно привести алгоритм разложения на простые множители и алгоритм Евклида.

4. O(N)

Алгоритмы с таким временем, как правило, перебирают все входные значения. В качестве примера можно привести поиск минимума или максимума значений. Такое время называется линейным. Так же есть огромный спектр задач, которые можно решить за линию (например задачи на суффиксы и префиксы, однако, опять же, зависит от условия задачи), в них нужно подумать над тем, как за один проход по входным данным найти ответ. Одной из моих любимых задач на эту тему является «Великое лайландское переселение» (можете попытаться решить ее по ссылке https://informatics.mccme.ru/mod/statements/view3.php?id=32666&chapterid=112736#1) позже будет разбор на нее.

5. O(N*log(N))

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

6. O(N?)

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

7. O(2^N)

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

8. O(N!)

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

Итак, мы разобрали основные виды асимптотики работы алгоритма в следующий раз мы поговорим о правилах ее вычисления. Ну а на этом на сегодня все, осталось только подписаться на Hello w#rld.

Источник: m.vk.com

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