Основные понятия и применяемая терминология
Сложность алгоритма – это понятие, характеризующее ресурсозатратность алгоритма, как временную (сколько времени нужно центральному процессору для обработки данных), так и связанную с памятью (какой объём памяти ЭВМ требуется для программной реализации алгоритма).
Поскольку эти ресурсы ограничены, то для программиста очень важно разрабатывать эффективные алгоритмы, то есть такие алгоритмы, которые позволят максимально сэкономить машинные ресурсы в процессе компьютерных вычислений.
Как правило, за эффективность алгоритма при решении какой-либо задачи в основном на практике отвечает скорость получения результата. Существуют специальные способы оценки алгоритмов, позволяющие примерно определить время их выполнения, а также сравнить различные алгоритмы по своей эффективности с точки зрения временной сложности, ещё называемой вычислительной сложностью.
Результатом оценки оптимальности алгоритмов по времени является соответствующая им функция сложности (трудоёмкости), которая напрямую зависит от количества входных данных, необходимых для выполнения алгоритма, то есть от так называемого размера самой задачи. Чаще всего, для работы некоторого алгоритма потребуется тем больше времени, чем больше размер задачи, к решению которой он применяется.
Размер задачи определяется в зависимости от специфики рассматриваемой задачи. Например, при составлении алгоритмов на умножение матриц размером задачи будет считаться наибольший порядок используемых матриц, а при работе в программе с одномерными массивами размер будет измеряться как максимальное из встречающихся количество элементов в массиве. Здесь можно привести и много других примеров. Так, при нахождении НОД двух чисел за размер задачи будет отвечать разрядность наименьшего числа, при вычислении значения некоторого многочлена – его степень, а при решении различных задач из области теории графов – число вершин и рёбер в рассматриваемых графах.
Часто оказывается, что сложность алгоритма зависит не только от размера входных данных, но и от самих этих данных. Это связано с тем, что общее количество элементарных операций, которые центральному процессору компьютера потребуется выполнить для решения определённой задачи при реализации некоторого алгоритма может значительно отличаться в зависимости от входных данных. Так, например, сортировка в массиве может быть выполнена быстрее, если его элементы уже изначально отсортированы.
В связи с этим принято рассматривать понятие временной сложности алгоритма в трёх случаях – наилучшем, наихудшем и среднем. На практике при анализе работы любого алгоритма рекомендуется ориентироваться на самый худший случай. В качестве примера такого наихудшего случая можно привести ситуацию, когда при поиске нужной информации в базе данных оказалось, что она вообще отсутствует в этой базе данных.
Классификация алгоритмов по их сложности
Обычно, рассматривая степень сложности алгоритмов, имеют в виду их асимптотическую сложность. Для определения значения этой характеристики оценивают скорость или порядок роста времени выполнения алгоритма при увеличении размера подаваемых к нему на вход данных, устремляя полученную величину на бесконечность.
Известно, что алгоритм, который в таком асимптотическом смысле является более эффективным, будет более производительным для любых входных данных, за исключением задач очень небольшого размера. Поэтому вычисление асимптотической сложности алгоритма позволит определить допустимый размер задач, которые можно решать с помощью него.
По своей вычислительной сложности все алгоритмы подразделяются на несколько классов. Рассмотрим самые основные из них:
- линейный – класс алгоритмов с временной сложностью, выражаемой некоторой линейной функцией от размера задачи;
- полиномиальный – класс алгоритмов, временная сложность которых задаётся некоторой полиномиальной функцией, зависящей от размера задачи;
- экспоненциальный – класс алгоритмов с временной сложностью, которая задаётся некоторой экспоненциальной функцией от размера задачи.
Анализ сложности алгоритмов
Различия между этими классами алгоритмов становятся явно заметными при решении задач значительно большого размера. В представленной ниже таблице показана скорость нарастания времени исполнения алгоритмов из различных классов в зависимости от объёма входных данных (при их реализации на компьютере с быстродействием 106 операций в секунду).
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Чтобы более подробно в общем виде представить такие различия, посмотрим на следующий рисунок, где изображены графики 6 функций, среди которых константа, линейная функция, квадратичная, кубическая, экспоненциальная функция и функция вида $log_2n$.
Рисунок 2. Графики функций. Автор24 — интернет-биржа студенческих работ
Здесь мы можем наглядно проследить скорость возрастания каждой из этих функций, а также сравнить их поведение между собой, заметив некоторые изменения при соотношении графиков экспоненциальной, квадратичной и кубической функций.
Это означает, что эффективность применяемых видов алгоритмов может несколько меняться в зависимости от аргумента функции сложности алгоритма, то есть от размера задачи. Это и было продемонстрировано в таблице, где сравнивались полиномиальные и экспоненциальные алгоритмы.
Далее приведём примеры полиномиальных и экспоненциальных алгоритмов:
- Именно полиномиальные алгоритмы считаются наиболее эффективными. Примерами полиномиальных алгоритмов являются стандартные алгоритмы целочисленного сложения, умножения, деления, нахождения НОД, перемножения матриц, сортировки массивов, поиска данных и некоторые другие алгоритмы.
- К экспоненциальным алгоритмам относятся алгоритмы построения всех подмножеств заданного множества или всех поддеревьев заданного графа. При этом многие экспоненциальные алгоритмы значительно отличаются друг от друга по своей эффективности.
Несмотря на то, что обычно задача считается сложной, если для её решения невозможно создать полиномиальный алгоритм, бывают и такие ситуации, в которых экспоненциальные алгоритмы оказываются довольно эффективными. Например, симплекс-метод, используемый для решения задач линейного программирования.
