Алгоритмическая сложность

Сложность - функция зависимости объема работы от размера входных данных O(f(N)).

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

Рассмотрим алгоритм вычисления значения многочлена степени n от заданной переменной x.

Алгоритм 1:
Для каждого слагаемого последовательным умножением возведем x в заданную степень и умножим на соответствующий коэффициент a. Затем сложим все слагаемые.

Вычисление n-го слагаемого требует n умножений, т.е. всего умножений 1 + 2 + 3 + ... + n = n*(n + 1)/2 и n + 1 сложение.

Т.е. всего операций получается (n^2)/2 + 3n/2 + 1

Алгоритм 2:
Вынесем x-ы за скобки и перепишем многочлен в виде

Будем вычислять выражение изнутри. Таким образом, на каждую скобку, которых всего n - 1 штук, приходится одно умножение и одно сложение. Затем умножим на оставшийся x и прибавим a0. Т.е. всего получится 2n операций.

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

Таким образом, ассимптотическая скрость функции f1(n) = (n^2)/2 + 3n/2 + 1 будет n^2, а у f2(n) = 2n скорость возростания равна n.

Для обозначения же временной сложности используются O(g(n)), Θ(g(n)), Ω(g(n)), где g(n) - асимптотическая функция.

O (верхняя граница, оценка худшего случая)

Рассмотрим функцию f(n) > 0 и ее ассимптотическую сложность g(n) > 0, где n > 0. Тогда если f(n) = O(g(n)) и существуют константы c > 0, n0 > 0, то 0 < f(n) < c*g(n), для
n > n0. Т.е. f(n) возрастает медленнее, чем функция g(n)

Таким образом O является верхней границей сложности алгоритма.

Θ (Тета - средняя оценка)

f(n) = Θ(g(n)), если существуют константы c1 > 0, c2 > 0, для которых c1*g(n) < f(n) < c2*g(n)

Т.е. f(x)=Θ(g(n)) означает, что f растет так же как и g

Ω (Омега - нижняя граница, оценка для лучшего случая)

f(n) = Ω(g(n)), если 0 < c*g(n) < f(n). Т.е. имеется ввиду, что f(n) растет не медленнее, чем g(n)

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

Равномерный весовой критерий (РВК) предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК) учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти.

Временная сложность при ЛВК определяется значением l(Op), где Op – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M), где M – величина ячейки памяти.

Пример оценки сложности при вычислении факториала

Необходимо проанализировать сложность алгоритма вычисление факториала n. Для этого напишем на псевдокоде языка С данную задачу:

void main() 
{
  int result = 1;
  const n = ...;
  
  for (int i = 2; i <= n; i++)
    result = result * n;
}

Временная сложность при равномерном весовом критерии

Достаточно просто определить, что размер входа данной задачи – n. Количество шагов – (n — 1).

Таким образом, временная сложность при РВК равна O(n).

Временная сложность при логарифмическом весовом критерии

В данном пункте следует выделить операции, которые необходимо оценить. Во-первых, это операции сравнения. Во-вторых, операции изменения переменных (сложение, умножение). Операции присваивания не учитываются, так как предполагается, что она происходят мгновенно.

Итак, в данной задаче выделяется три операции:

1) i <= n

На i-м шаге получится log(n). Т.к. шагов (n-1), сложность данной операции составит (n-1)*log(n).

2) i = i + 1

На i-м шаге получится log(i). Таким образом, получается сумма:

3) result = result * i

На i-м шаге получится log((i-1)!). Таким образом, получается сумма

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

Ёмкостная сложность при равномерном весовом критерии

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

Так как количество переменных не зависит от размера входа, сложность будет равна O(1).

Ёмкостная сложность при логарифмическом весовом критерии

В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение Vmax.

В данной задаче существует переменная, значение которой не превосходит n (i), и переменная, значение которой не превышает n! (result). Таким образом, оценка равна O(log(n!)).