Сложность алгоритмов

Назначение анализа сложности алгоритмов — оценка того как ведет себя алгоритм при увеличении объема входящих данных. Анализ сложности может быть проведен с точки зрения скорости выполнения алгоритма и объема потребляемой памяти.

О-большое

Для анализа сложности применяется специальная математическая нотация — О-большое. О-большое определяет порядок роста в худшем случае. Это означает, что для алгоритма со сложностью $O (n)$ при увеличении входных данных в 3 раза потребуется в 3 раза больше времени на выполнение, а для алгоритма со сложностью $O (n^{2})$ при таким же увеличении входных данных в 3 раза время выполнения увеличится уже в $3^{2} = 9$ раз.

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

Часто встречаемые порядки сложности алгоритмов:

$O (l o g_{2} (n))$
$O (n)$
$O (n * l o g_{2} (n))$
$O (n^{2})$
$O (n!)$

Сложность и физические характеристики

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

Константы в О-большом

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

Например, есть два алгоритма со сложностью $O (c * n^{2})$ и $O (k * n)$ . Константы $c$ и $k$ не используются в расчете О-большого, но в реальных алгоритмах они могут означать количество операций (сравнений, присваиваний и др.). Если $c = 2$ , а $k = 100$ . то при размере входных данных равном 10, алгоритмы будут выполнятся за 200 и 1000, получается, что алгоритм со сложностью $O (n)$ выполняется быстрее. Но если размер данных увеличится до 100, то соотношение изменится: 100000 и 1000. При росте входных данных разница будет только расти.

Использование нотации О-большое

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

Другое назначение нотации — способ сравнения алгоритмов между собой.

Ссылки

Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 1. Знакомство с алгоритмами. «О-большое»
Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 4. Быстрая сортировка. Снова об «О-большом»

Ссылки на эту заметку

Эта заметка на GitHub

Обсудить на форуме

# Сложность алгоритмов

# О-большое

# Сложность и физические характеристики

# Константы в О-большом

# Использование нотации О-большое

# Ссылки