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

Пространство — время

Многие алгоритмы предоставляют выбор между скоростью выполнения и используемыми программой ресурсами. Задача может выполняться быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший объем памяти. Из этой связи вытекает идея пространственно-временной сложности алгоритмов. При этом подходе сложность алгоритма оценивается в терминах времени и пространства, и находится компромисс между ними.

Оценка с точностью до порядка

При сравнении различных алгоритмов важно понимать, как сложность алгоритма соотносится со сложностью решаемой задачи. Различие производительности алгоритмов на задачах разной вычислительной сложности часто более важно, чем просто скорость алгоритма. Производительность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность порядка O(f(N)) (произносится “О большое от F от N”), если время выполнения алгоритма растет пропорционально функции f(N) с увеличением размерности исходных данных N. При оценке порядка сложности алгоритмов используется только наиболее быстро растущая часть уравнения алгоритма. Допустим, время выполнения алгоритма пропорционально N3+N. Тогда сложность алгоритма будет равна O(N3). Постоянные множители в соотношении также игнорируются.

Поиск сложных частей алгоритма

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

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

Сложность рекурсивных алгоритмов

Рекурсивными процедурами (recursive procedure) называются процедуры, вызывающие сами себя. Во многих рекурсивных алгоритмах именно степень вложенности рекурсии определяет сложность алгоритма, при этом не всегда легко оценить порядок сложности. Рекурсивная процедура может выглядеть простой, но при этом вносить большой вклад в сложность программы, многократно вызывая саму себя.

Многократная рекурсия

Рекурсивный алгоритм, вызывающий себя несколько раз, является примером многократной рекурсии (multiple recursion). Процедуры с множественной рекурсией сложнее анализировать, чем просто рекурсивные алгоритмы, и они могут давать больший вклад в общую сложность алгоритма.

Требования рекурсивных алгоритмов к объему памяти

Для некоторых рекурсивных алгоритмов важен объем доступной памяти. Можно легко написать рекурсивный алгоритм, который будет запрашивать небольшой объем памяти при каждом своем вызове. Объем занятой памяти может увеличиваться в процессе последовательных рекурсивных вызовов.

Поэтому для рекурсивных алгоритмов необходимо хотя бы приблизительно оценивать требования к объему памяти, чтобы убедиться, что программа не исчерпает при выполнении всю доступную память.