Оценка временной сложности алгоритмов

При проектировании алгоритмов, как правило, не представляет интереса точное число шагов, необходимых для решения задачи на конкретном наборе данных. Гораздо важнее знать, как будет изменяться время решения задачи T, если размер входа n растёт.

Класс алгоритмов, время работы которых растёт, по крайней мере, так же быстро, как некоторая функция f(n), обозначается как Ω(f(n)). Это означает, что при всех n, превышающих порог n₀, T(n) ≥ C^.f(n) для некоторого положительного числа C. Оценка времени работы снизу может представлять интерес только как теоретическая нижняя граница эффективности любого алгоритма для некоторой задачи, которую преодолеть невозможно.

Класс алгоритмов, время работы которых растёт не быстрее функции f(n), обозначается O (f(n)), что означает существование положительных чисел n₀ и c таких, что при n > n₀ T(n) ≤ C^.f(n). Этот класс — важнейшая характеристика алгоритма, его временная сложность. По скорости роста этого времени в зависимости от размера входа алгоритмы делятся на следующие классы временной сложности:

— алгоритмы константной сложности — T(n) ∈ O(1);

— логарифмической сложности — T(n) ∈ O(log n);

— линейной сложности — T(n) ∈ O(n);

— квадратичной сложности — T(n) ∈ O(n²);

— кубической сложности — T(n) ∈ O(n³);

— полиномиальной сложности — T(n) ∈ O(n^k), где k = const; k = 0, 1, 2 или 3 — это частные случаи классов полиномиальной сложности;

— экспоненциальной сложности — T(n) ∈ O(aⁿ).

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

Алгоритм, для которого оценки Ω(f(n) и O (f(n)) совпадают, называется оптимальным. Так, очевидно, что алгоритм, имеющий на входе некоторое множество, будет оптимальным, если его временная сложность O (1). Такой алгоритм можно попытаться найти, если задача не требует рассмотреть множество целиком. Если же требуется что-то сделать с каждым элементом множества мощностью n, оптимальный алгоритм будет иметь сложность O (n). Если имеется два множества, и нужно обработать все возможные пары их элементов, можно ожидать сложности O (n²), для трёх множеств, если обрабатываются все тройки — O (n³), и т. д.

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

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

— для самого неудобного набора данных — сложность «в худшем случае»;

— для типового набора данных — сложность «в среднем».

Тривиальные входные данные («лучший случай») обычно интереса не представляют.

Для оценки временной сложности по реализации алгоритма (тексту программы) можно руководствоваться следующими соображениями:

— операции присваивания (копирования) и проверки условия для базовых типов данных выполняются за константное время. Если при этом вызывается функция, сложность шага алгоритма определяется сложностью функции (в операциях с объектами функции могут вызываться неявно);

— сложность алгоритма, состоящего из последовательности шагов, определяется по самому сложному шагу;

— сложность выбора по условию определяется по самой сложной из альтернатив. В порядке исключения можно не принимать во внимание альтернативы, выбираемые очень редко. Можно учесть такие альтернативы, как «худший случай»;

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

— рекурсия рассматривается как тот же цикл. Её сложность определяется как произведение сложности одного вызова функции на количество вызовов.

Пример 1. Вычислить b = (a ∈ A), где множество A мощностью nA представлено массивом целых чисел.

Решение: b = false; for (i = 0;!b && (i < nA); i++) b |= (a == A[i]);

Временная сложность алгоритма — O (nA). Если элемент a найден, алгоритм прекращает работу, выполнив от 1 до nA шагов. В среднем количество шагов будет nA / 2, в худшем случае (a ∉ A) — nA.

Пример 2. Вычислить C = A ⋂ B для множеств, представленных неупорядоченными массивами.

Решение: проверяем все возможные пары элементов двух множеств и отбираем совпадения.

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++) if (A[ i ] == B[ j ]) C[ k++ ] = A[ i ];

Проверка на совпадение и присваивание выполняются за константное время, поэтому сложность алгоритма — O (nA × nB), или O (n²), где n — средняя мощность множеств.

Пример 3. Вычислить D = A ⋂ B ⋂ C.

Очевидное решение

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++)

for (r = 0; r <nC; r++)

if ((A[ i ] == B[ j ]) && (A[ i ] == C[ r ])) D[ k++ ] = A[ i ];

имеет временную сложность O (n³), поскольку перебираются все возможные тройки. Однако перебирать все тройки никакой необходимости нет.

Модифицируем алгоритм:

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++)

if (A[i] == B[j]) for (r = 0; r <nC; r++)

if (A[i] == C[r]) D[k++] = A[i];

В алгоритме по-прежнему три вложенных цикла, но внутренний цикл теперь зависит от условия A[ i ] == B[ j ], которое проверяется n² раз, но удовлетворяется не более чем n раз, т. е. рассматриваются только такие тройки, у которых первые два элемента совпадают. Проверка A[i] == C[r] выполняется, таким образом, не более n² раз, и общая сложность алгоритма — O (n²).

Пример 4. Вычислить C = A ⋂ B для множеств, представленных строками символов.

Решение:

for(i = k = 0; i < strlen(A); i++)

for (j = 0; j < strlen(B); j++) if (A[ i ] == B[ j ]) C[ k++ ] = A[ i ];

По аналогии с примером 2 можно оценить сложность как O (n²). Однако это неверно, так как в обоих циклах по n раз вычисляется функция определения длины строки strlen(), которая, очевидно, подсчитывает в строке количество символов до ближайшего нуля перебором, т. е. имеет линейную сложность. Вычисление этой функции — один из шагов внутренней части обоих циклов. Таким образом, внутренняя часть вложенного цикла состоит из трёх шагов, двух константных (проверка и присваивание) и линейного (вычисление функции). С учётом n повторений сложность всего цикла — O (n²). Внешний цикл добавляет сюда ещё шаг вычисления функции сложностью O (n). Сложность его внутренней части — O (n²), а всего алгоритма — O (n³)! Это — цена экономии двух целых переменных. На самом деле нужно вычислить nA = strlen(A); nB = strlen(B), а затем использовать алгоритм из примера 2.

Редактор Г. Г. Петров

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Подписано в печать. Формат 60×84 1/16.

Бумага офсетная. Печать офсетная. Печ. л. 4,0.

Гарнитура «Times». Тираж экз. Заказ

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Издательство СПбГЭТУ «ЛЭТИ»

197376, С.-Петербург, ул. Проф. Попова, 5