Часто встречающиеся функции оценки порядка сложности

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

==============9

@Таблица 1.2. Часто встречающиеся функции оценки порядка сложности

Сложность алгоритма, определяемая уравнением, которое представляет собой сумму функций из таблицы, будет сводиться к сложности той из функций, которая расположена в таблице ниже. Например, O(log(N)+N²) — это то же самое, что и O(N²).

Обычно алгоритмы со сложностью порядка N*log(N) и менее сложных функций выполняются очень быстро. Алгоритмы порядка N^C при малых C, например N² выполняются достаточно быстро. Вычислительная же сложность алгоритмов, порядок которых определяется функциями C^N или N! очень велика и эти алгоритмы пригодны только для решения задач с небольшим N.

В качестве примера в табл. 1.3 показано, как долго компьютер, выполняющий миллион инструкций в секунду, будет выполнять некоторые медленные алгоритмы. Из таблицы видно, что при сложности порядка O(C^N) могут быть решены только небольшие задачи, и еще меньше параметр N может быть для задач со сложностью порядка O(N!). Для решения задачи порядка O(N!) при N=24 потребовалось бы время, большее, чем время существования вселенной.

Логарифмы

Перед тем, как продолжить дальше, следует остановиться на логарифмах, так как они играют важную роль в различных алгоритмах. Логарифм числа N по основанию B это степень P, в которую надо возвести основание, чтобы получить N, то есть B^P=N. Например, если 2³=8, то соответственно log₂(8)=3.

==================10

@Таблица 1.3. Время выполнения сложных алгоритмов

Можно привести логарифм к другому основанию при помощи соотношения log_B(N)=log_C(N)/log_C(B). Например, чтобы вычислить логарифм числа по основанию 10, зная его логарифм по основанию 2, можно воспользоваться формулой log₁₀(N)=log₂(N)/log₂(10). При этом log₂(10) — это табличная константа, примерно равная 3,32. Так как постоянные множители при оценке сложности алгоритма можно опустить, то O(log₂(N)) — это же самое, что и O(log₁₀(N)) или O(log_B(N)) для любого B. Поскольку основание логарифма не имеет значения, часто просто пишут, что сложность алгоритма порядка O(log(N)).

В программировании часто встречаются логарифмы по основанию 2, что обусловлено применяемой в компьютерах двоичной системой исчисления. Поэтому мы для упрощения выражений будем везде писать log(N), подразумевая под этим log₂(N). Если используется другое основание алгоритма, это будет обозначено особо.

Реальные условия — насколько быстро?

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

Допустим, мы рассматриваем два алгоритма решения одной задачи. Один выполняется за время порядка O(N), а другой — порядка O(N²). Для больших N первый алгоритм, вероятно, будет работать быстрее.

Тем не менее, если взять конкретные функции оценки времени выполнения для каждого из двух алгоритмов, например, для первого f(N)=30*N+7000, а для второго f(N)=N², то в этом случае при N меньше 100 второй алгоритм будет выполняться быстрее. Поэтому, если известно, что размерность данных задачи не будет превышать 100, возможно будет целесообразнее применить второй алгоритм.

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

==================11

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

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

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