Сложность вычислений

Выбор алгоритмической модели существенно влияет на сложность вычисления задачи. Сложность вычисления есть функция, дающая числовую оценку трудоемкости применения алгоритма к исходным данным для получения искомого результата. Чаще всего рассматривают временнýю сложность и ёмкостнýю, которые, как правило, представляются функциями от |x|, где |x| – мощность множества исходных данных.

Время вычисления описывается произведением числа шагов алгоритма от исходных данных до искомого результата и средним физическим временем реализации одного шага. Число шагов определяется описанием алгоритма в заданной алгоритмической модели.

Пусть машина Тьюринга вычисляет некоторую функцию f(x) данного класса задач. Тогда t(x) есть функция, равная числу шагов при вычислении f(x), если f(x) определена. Функция t(x) называется временнóй сложностью. Однако физическое время реализации одного шага алгоритма на конкретном компьютере зависит от типа компьютера, способов компиляции, скорости обработки информации, что существенно усложняет определение временнóй сложности.

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

Пусть машина Тьюринга вычисляет функцию f(x). Тогда s(x) есть функция, равная множеству всех ячеек информационной ленты, которые, если f(x) определена, посещаются в процессе вычисления этой функции. Функция s(x) называется ёмкостнóй сложностью.

Если машина Тьюринга имеет внешнюю и внутреннюю памяти мощности n =| V_t | и m=|Q| соответственно, то для временнóй и ёмкостнóй функций сложности допустимы оценки:

s(x)£ | x |+ t(x),

t(x)£ m*s² (x)| n^s(x)

Чаще всего временнýю сложность t(x) описывают полиномами от исходных данных. Если известен размер исходных данных - |x| и временная сложность задана некоторым полиномом t(|x|) = р(|x|), то оценка временнóй сложности есть O(р(|x|)). Эта оценка определяется, как правило, старшим членом полиномиального ряда. При этом говорят, что машина Тьюринга решает задачу за полиномиальное время. Например, если временнáя сложность задана полиномом р(|x|) = 4|x|² + 7|x| + 12, то оценка временной сложности есть О(|x|²). Алгоритм, имеющий полиномиальное время, называют полиномиальным алгоритмом. Множество однотипных задач, разрешаемых на машине Тьюринга за полиномиальное время, принадлежит классу задач Р.

Есть задачи, для которых может быть найдено некоторое слово α, являющееся догадкой (или удостоверением) принадлежности задачи к классу Р на недетерминированной машине Тьюринга. В этом случае говорят, что задача принадлежит к классу NP, а оценка временной сложности есть O(p(α)).

Если t(|x|) ≥ O(p(|x|)), то говорят, что машина Тьюринга решает задачу за экспоненциальное время t(|x|) = O(c^|x|), где с – некоторая константа. Например, для булевых функций с = 2. Тогда t(n) = O(2ⁿ), где n - число булевых переменных.

Пример1. Дано N = {1, 2, 3,…, n} и R ⊆ N Ä N. Является ли R отношением эквивалентности?

Известно, что R является отношением эквивалентности тогда и только тогда, когда выполнены условия:

1, если (i, j)ÎR и (j, i)ÎR,

r(i, j) = 1, если i=j,

0, если (i, j) Ï R.

Дополнительным условием является r²(i, j) ≥ r(i, j).

Проверка этих условий ограничена независимыми оценками O(n²) и O(n), так как нужно вычислять значения r²(i, j) для каждой пары (i, j), а затем сравнивать с r(i, j). Оценка временнóй сложности задачи есть O(n⋅n²) = O(n³). Поэтому алгоритм данной задачи есть полиномиальный, а оценка его временнóй сложности зависит от числа исходных данных в третьей степени.

Пример2. Дано N = {1, 2, 3,…, n} и R = {(1, 2), (2, 3), (3, 4),…, (n, 1)} ⊆ N Ä N. Является ли R отношением эйлеровым?

Бинарное отношение R называют эйлеровым, если элементы R можно упорядочить (i₁, i₁), (i₂, i₂),…, (i_n, i_n), где n = |R|, и выполнить условие (i₁, i₂) ∈ R, (i₂, i₃) ∈ R,…, (i_n, i₁) ∈ R.

Связное отношение R является эйлеровым тогда и только тогда, когда число единиц в матрице R совпадает в i-м столбце и i-й строке для каждого i ∈{1,2..,n}.

Так как все вычисления выполняются только с одной матрицей R, сравнивая число единиц в i-й строке и i-м столбце, то временнáя сложность задачи будет O(n²). Поэтому алгоритм данной задачи полиномиальный, а оценка его временнóй сложности зависит от числа исходных данных во второй степени.

[1] Здесь и далее N – множество натуральных чисел