Сложность алгоритма
Математический анализ любого алгоритма всегда неразрывно связан с понятием сложности. Различают временную и пространственную сложности алгоритма. Понятие пространственной сложности довольно простое и практически полностью повторяет конструкцию временной, потому понятию пространственной сложности в этом разделе будет уделено мало внимания.
Итак, остановимся на понятии временной сложности алгоритма. Понятно, что речь идет о времени, то есть, так или иначе, о скорости работы алгоритма. В информатике важно не просто решить задачу — важно решить ее как можно более эффективно. Потому нужен формальный инструмент, при помощи которого мы могли бы сравнивать алгоритмы, решающие одну и ту же задачу, между собой и выбирать из них лучший.
Здесь нужно обратить внимание, что, не смотря на принципы олимпиадного программирования, идея засечь секундомером время, которое потребовалось алгоритму для решения задачи, совершенно не подходит для этих целей (и тем самым подобная характеристика не может называться временной сложностью).
Рассмотрим некоторый алгоритм $\mathcal{A}$. Алгоритм всегда формулируется на языке исполнителя, то есть всегда ориентирован на конкретного исполнителя. Существуют разные теоретические исполнители: машина Тьюринга, алгоритмы Маркова, RAM-машина. В каждой из этих моделей подробно описывается, из чего она состоит и как происходит выполнение алгоритма, а также описывается набор так называемых элементарных действий, которые может совершать этот исполнитель (сдвинуть головку вправо, сделать запись, сделать замену подстроки, записать в определенный регистр и т.д.). Большинство студентов представляют себе алгоритм как код на языке Python или С++, что в принципе, совершенно естественно. Элементарными тогда называют, как правило, очень простые атомарные действия: присваивание, арифметические операции, сравнения, обращение по индексу к элементу массива и др. Нужно понимать, что это некоторая вольность, которая снижает степень математической строгости, но так делать можно. (На самом деле, в случае, например, С++, код всегда переводится в процессе компиляции в язык ассемблера, система команд которого очень похожа на элементарные команды RAM-машины. То есть с некоторой точностью можно установить соответствие между простыми командами С++, которые мы назвали элементарными, и элементарными действиями настоящей математической модели вычислений.) Сформулируем теперь важнейшее определение.
Заметим, что функция очень абстрактная: она определена для любого корректного входа любой длины. Такой объект анализировать крайне трудно, поэтому обычно вводят еще несколько определений.
Рассмотрим теперь множество потенциальных входных данных для нашего алгоритма $\texttt{Inputs}$. На этом множестве всегда можно ввести некоторую числовую характеристику «длину входа» $\texttt{len}$. Например, если на вход подается одно единственное число, то можно рассмотреть количество десятичных разрядов в нем (а лучше количество двоичных), а если на вход подаются числа для обработки — рассмотреть количество этих чисел. Эта характеристика всегда выбирается отдельно для анализа каждой задачи. Таким образом, можно разбить все входы на непересекающиеся множества входов определенной длины:
\[\texttt{Inputs} = \texttt{Inputs}_{\texttt{len=1}} \,\sqcup\, \texttt{Inputs}_{\texttt{len=2}} \,\sqcup\, \ldots \,\sqcup\, \texttt{Inputs}_{\texttt{len}=n}\,\sqcup\,\ldots\]Тогда мы можем составить более простые функции.
Таким образом мы получаем функцию $f(n)$ от длины входных данных. Определение совершенно естественно: для сложности в худшем случае мы зафиксируем определенную длину $n$, и рассмотрим, в каком-то смысле, «самые плохие» входные данные $\texttt{input}\in\texttt{Inputs}_{\texttt{len}=n}$ длины $n$, дающие самое большое количество элементарных действий $T^{\mathcal{A}}(\texttt{input})$.
Определение сложности в лучшем случае аналогично, только по всем входам фиксированной длины берется минимум, а не максимум. Такой вид сложности обычно представляет меньший интерес: зачем нам знать факт, что на каком-то отдельном $\texttt{input}$ алгоритм работает хорошо (при том, что, возможно, на всех остальных $\texttt{input}$ плохо).
Рассмотрим следующий пример кода: линейный поиск элемента $x$ в массиве $\mathbf{a}$.
for (int i = 0; i < n; ++i) {
if (a[i] == x) return i;
}
return i;
Если обозначить позицию элемента $x$ в массиве $\mathbf{a}$ (или ответ на задачу) как $k$, то можно вычислить, что мы выполняем
- изначально одно присваивание
i=0; - затем $k+1$ сравнение в условии
forи $k$ раз делаем++i; - мы так же сделаем $k+1$ сравнение внутри
ifи $k+1$ раз обратимся по индексуa[i], если элемент в массиве есть, и сделаем $k$ сравнений внутриifи $k$ раз обратимся по индексуa[i], если элемента в массиве нет.
Складываем все это и получаем, что
\[T^{\mathcal{Linear Search}}(\mathbf{a}, x) = \begin{cases} 4k+4,\,\text{если элемент } x \text{ в массиве есть,}\\ 4k+2,\,\text{если элемент } x \text{ в массиве отсутствует.} \end{cases}\]Заметим, что худшими будут входные данные, при которых элемент $x$ будет отсутствовать: $k=n$. Получаем, что в худшем случае сложность алгоритма равна:
\[f^{\texttt{worst}}(n) = 4n+2.\]Очевидно, в лучшем случае, когда элемент $x$ находится в самом начале, сложность получается
\[f^{\texttt{best}}(n) = 4.\]Как видно, вывести явные функции сложности в худшем случае даже для такого простого алгоритма, как линейный поиск, оказывается весьма трудоемкой задачей. Функции почти всегда получаются некрасивыми, громоздкими, с условиями. Более того, выписать явно функцию $T^{\mathcal{A}}$ чаще просто невозможно (это нам так повезло, что был выбран достаточно тривиальный алгоритм). К счастью, явный вид этих функций практически никогда не нужен: достаточно лишь указать оценку сверху на эти функции. Математическим способам оценки функций будет посвящен следующий раздел.