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

Сложность алгоритма помогает оценить затраты на его реализацию и определяется вычислительными мощностями, необходимыми для его выполнения. Она часто измеряется двумя параметрами: T(временная сложность) и S (пространственная сложность, или требования к памяти). И T и S обычно представляются в виде функций от n, где n – размер входных данных.

Пусть А – алгоритм для решения некоторого класса задач, а n – размерность отдельной задачи из этого класса. В общем случае n может быть длиной обрабатываемой последовательности данных. Определим f(n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т.д.), которые должен выполнить алгоритм.

Определим асимптотическую сложность алгоритма А. Если алгоритм обрабатывает входную последовательность (ВХП) размера n за время cn², то говорят, что временная сложность этого алгоритма – Q(n²) (читается: порядка n²). Точный смысл этого утверждения такой: найдутся такие константы c1, c2 > 0 и такое число n0, что c₁n² ≤ f(n) ≤ c₂n² при всех n ≥ n₀. Вообще, если g(n) – некоторая функция, то запись f(n) = Q(g(n)) означает, что найдутся такие c1, c2 > 0 и такое n₀, что c₁g(n) ≤ f(n) ≤ c₂g(n) при всех n ≥ n₀.

Запись f(n) = Q(g(n)) включает в себя две оценки – верхнюю и нижнюю. Их можно разделить (в данном случае нас больше интересует верхняя оценка). Говорят, что f(n) = O(g(n)), если найдется такая константа > 0 и такое число n₀, что 0 ≤ f(n) ≤ cg(n) для всех n ≥ n₀. Также существуют определения:

Функция f(n) является O[g(n)] (о-большое) для больших n, если:

Функция f(n) является o[g(n)] (о-малое) для больших n, если:

Говорят, что алгоритм А – полиномиальный, если f(n) растет не быстрее, чем полином от n. При этом в качестве g(n) оставляют член, быстрее всего растущий при увеличении n. При этом все члены низших порядков игнорируются.

Пример: Если временная сложность алгоритма описывается как T(n) = 4n² + 7n + 12, то вычислительная сложность определяется, как O(n²).

Временная сложность, определяемая таким образом не зависит от реализации. Не нужно знать ни точное время выполнения различных инструкций, ни число битов, используемых для представления различных переменных, ни даже скорость процессора. Один компьютер может быть на 50 процентов быстрее другого, у третьего шина данных может быть в два раза быстрее, но сложность алгоритма, оцененная по порядку величины, не изменится. Запись оценки сложности позволяет увидеть, как объем входных данных влияет на требования ко времени выполнения. Например, если T(n) = O(n), то удвоение входных данных удвоит и время работы алгоритма. Если T = O(2ⁿ), то добавление одного бита к входным данным удвоит время выполнения.