Статья является продолжением статьи Алгоритмы - Сложность алгоритмов. Введение, многое в текущей статье является конкретизацией, а в некоторых случаях перечеркивыванием всего старого для уточнения применения сложности алгоритма сразу на всех процессорах и языках программирования.

Алгоритмы - Сложность алгоритмов. Основы

В статье "Алгоритмы - Сложность алгоритмов. Введение" рассказывалось, как получить точную оценку алгоритма.

Каждый алгоритм представляет собой набор команд в последовательности времени выполнения и зависит от количества входных данных, к примеру, массив arr[n] размерностью n. Сложность алгоритма обозначается f(n). f(n) представляет собой сумму операторов или комманд процессора, которые выполняются в потоке времени. Допустим f(n) = 10n² + 1,553n + 15, в зависимости от размера входных данных (размера arr[n] равному n). Нужно дать математическую оценку вне зависимости от языка программирования, ассемблера и процессора, т.к. f(n) точная для каждого одного и того же алгоритма в разных случаях будет разная. Для оценки сложности алгоритма берут наибольшее слагаемое полинома f(n) без констант, так учитывается различие языков программирования и процессоров, к тому же алгоритм может быть описан на естественном языке.

Перечислим наиболее часто встречаемые сложности алгоритмов привиденные по возрастанию сложности (вычислительной сложности):

• log(n) — сублинейная сложность;
• n — линейная сложность сложность;
• nlog(n) — субстепенная сложность;
• n^r — степенная сложность (r — константа);
• rⁿ — експонециальная сложность (r — константа);
• n! — факториальная сложность.

Далее представлен график степеней сложности:

Рис. 1. График степеней сложности.

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

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

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

Заключение

Эти знания являются текущими на настоящий момент. В заключение могу Вам пожелать прочитать книгу Дж. Клейнберга и Е. Тадоса "Алгоритмы. Разработка и применение" для более конкретного понимания.