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

Для решения одной и той же задачи часто можно придумать более одного алгоритма. В связи с чем, возникает вопрос: какой из алгоритмов “лучше”?

В большинстве случаев, “лучше”, видимо, такой алгоритм, который на тех же входных данных приходит к решению задачи, потребляя меньшее количество вычислительных ресурсов (памяти и времени). Это, конечно, нестрогое рассуждение. Для более строгого рассуждения введем несколько понятий.

Вычислительный процесс алгоритма: это последовательность шагов, пройденная при исполнении алгоритма для некоторых входных данных.

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

Временна́я сложность алгоритма: это время \(T\), необходимое для завершения вычислительного процесса алгоритма для некоторых входных данных.

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

Однако можно время \(T\) выразить через количество элементарных действий \(k\) и среднее время выполнения элементарного действия \(t\):

\[T=k t\]

При этом, \(k\) является свойством самого алгоритма, а \(t\) – свойством исполнителя.

Ввиду того, что \(t\) можно считать константой для данного исполнителя, обычно сложность алгоритмов оценивается с точностью до константного множителя. Другими словами, сложность алгоритма оценивается порядком роста.

Порядок роста: положительно-определенная функция \(g(x)\) имеет порядок роста \(f(x)\) (записывается \(g(x)=\mathcal{O}(f(x))\)), если \(\exists c>0 : \: \forall x>x_0, \, g(x) \leq c f(x)\).

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

Так, например, чтение данных и сохранение их в памяти в виде массива будет иметь сложность \(\mathcal{O}(n)\), или линейную сложность, а умножение матриц уже кубическую \(\mathcal{O}(n^3)\).

Кроме времмено́й сложности алгоритма, важной оказывается так же пространственная сложность алгоритма.

Пространственная сложность алгоритма: это количество дополнительной памяти \(S\), которое алгоритм требует для работы. Память \(D\), необходимая для хранения входных данных, не включается в \(S\).

\(S\) в общем случае тоже зависит от исполнительного устройства. Скажем, если два исполнительных устройства поддерживают целые длинной 4 и 8 байт соответственно, то пространственная сложность алгоритма на 8-байтных целых будет вдвое больше, чем на 4-байтных целых. Поэтому пространственная сложность оценивается так же порядком роста.

Классы сложности алгоритмов

Выделяются определенные классы сложности: это категории, которые имеют схожую сложность.

Выделяют следующие основные классы сложности:

DTIME: Машина Тьюринга находит решение задачи за конечное время (количество шагов). Часто уточняется асимптотика алгоритма, так, скажем, если порядок роста времени работы \(T(n) = \mathcal{O}(f(n))\), то указывают \(DTIME(f(n))\).
P: Машина Тьюринга находит решение задачи за полиномиальное время (количество шагов), т.е. \(T(n) = \mathcal{O}(n^k)\), где \(k\in \mathbb{N}\). \(P=DTIME(n^k)\)
EXPTIME: Машина Тьюринга находит решение задачи за экспоненциальное время (количество шагов), т.е. \(T(n) = \mathcal{O}(2^{n^k})\), где \(k\in \mathbb{N}\). \(EXPTIME=DTIME(2^{n^k})\).
DSPACE: Машина Тьюринга находит решение задачи, используя конечное количество дополнительной памяти (ячеек). Часто уточняется асимптотика алгоритма, так, скажем, если порядок роста потребления памяти \(S(n) = \mathcal{O}(f(n))\), то указывают \(DSPACE(f(n))\).
L: Машина Тьюринга находит решение задачи c логарифмической пространственной сложностью, то есть \(S(n) = \mathcal{O}(\log n)\). \(L=DSPACE(\log n)\).
PSPACE: Машина Тьюринга находит решение задачи c полиномиальной пространственной сложностью, то есть \(S(n) = \mathcal{O}(n^k)\), где \(k\in \mathbb{N}\). \(PSPACE=DSPACE(n^k)\).
EXPSPACE: Машина Тьюринга находит решение задачи c экспоненциальной пространственной сложностью, то есть \(S(n) = \mathcal{O}(2^{n^k})\), где \(k\in \mathbb{N}\). \(EXPSPACE=DSPACE(2^{n^k})\).

Кроме того, существуют теоретические классы сложности, которые оперируют понятием недетерменированной машины Тьюринга (НМТ). Их определения совпадают с вышеприведенными, с заменой машины Тьюринга на НМТ, а названия имеют префикс N (например NP), кроме NTIME и NSPACE, где D заменяется на N.

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

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

Известно, что \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

Кроме того, \(P \subsetneq EXPTIME\), \(NP \subsetneq NEXPTIME\), \(PSPACE \subsetneq EXPSPACE\)

Так же известно, что если \(P = NP\), то \(EXPTIME = NEXPTIME\).

Вопрос равенства P и NP является одним из главных нерешенных вопросов современной информатики.

Примеры алгоритмов

Приведем несколько примеров простых алгоритмов и рассмотрим их сложность.

Возведение в целую степень

Этот алгоритм был описан в Древней Индии еще до нашей эры и используется для вычисления натуральной степени \(n\) вещественного числа \(x\)

Записать \(n\) в двоичной системе счисления
Заменить в этой записи каждую из 1 парой букв КХ, а каждый 0 – буквой К
Вычеркнуть крайнюю левую пару КХ
Читая полученную строку слева направо, встречая букву К возвести результат в квадрат, а встречая букву X – умножить результат на x. В начале результат равен x.

В этом алгоритме, мы имеем число операций умножения, равное количеству цифр в двоичном представлении \(n\) в лучшем случае, и \(2(n-1)\) в худшем случае. В любом случае, временная сложность \(T(n) = \mathcal{O}(\log n)\).

Дополнительной памяти в эффективной реализации алгоритма практически не требуется, и она не зависит от входных данных, поэтому пространственная сложность \(S(n) = \mathcal{O}(1)\).

Следует заметить, что существуют более эффективные алгоритмы. Однако по сравнению с “наивной” реализацией, требующей \(\mathcal{O}(n)\) операций умножения, этот алгоритм сравнительно эффективен.

Умножение целых

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

Первый множитель последовательно умножается на два, а второй – делится нацело на 2. Результаты записываются в два столбика, пока во втором не получится 1.

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

Поскольку целочисленное деление и умножение на 2 можно реализовать сдвигом, этот алгоритм дает \(2 \log_2 n\) операций сдвига, где \(n\) – меньшее из двух чисел. В худшем случае так же получается \(\log_2 n - 1\) операций сложения. В любом случае, временная сложность \(T(n) = \mathcal{O}(\log n)\).

Для эффективной реализации алгоритма, дополнительной памяти практически не требуется, и она не зависит от входных данных, поэтому \(S(n) = \mathcal{O}(1)\)

Опять же, следует заметить, что существуют более эффективные алгоритмы. Однако по сравнению с “наивной” реализацией, требующей \(\mathcal{O}(n)\) операций сложения, этот алгоритм сравнительно эффективен.

Пример

Умножение 23 на 43.

Возьмем 23 в качестве второго множителя.

43	23	нечетное
86	11	нечетное
172	5	нечетное
344	2
688	1	нечетное

Результат \(43+86+172+688 = 989\)

Получили 10 операций сдвига и 4 операции сложения. Для справки, \(\log_2(23) \approx 4.52\).

Алгоритмы поиска

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

Линейный поиск

Имеется массив \(a\) размера \(n\) (индексация с 1), требуется найти элемент массива равный \(P\).

Алгоритм:

Установить \(k:=1\)
Если \(k<n\), перейти к шагу 3, иначе алгоритм завершён неудачно
Если \(a_k = P\), вывести \(k\), алгоритм завершён удачно
Иначе, если \(k<n\), \(k:=k+1,\) перейти к шагу 2

Блок-схема алгоритма

Поскольку алгоритм проходит в худшем случае весь массив, сложность \(\mathcal O(n)\) операций сравнения.

Поиск минимального элемента

Имеется массив \(a\) размера \(n\) (индексация с 1), требуется найти минимальный элемент.

Алгоритм:

Установить \(k:=1\), \(μ:=a_1\)
Если \(k<n\), перейти к шагу 3, иначе, вывести \(μ\), алгоритм завершён
\(k:=k+1,\)
Если \(a_k < μ\), \(μ:=a_k\)
перейти к шагу 2

Блок-схема алгоритма

Сложность алгоритма \(\mathcal O(n)\)

Бинарный поиск в упорядоченном массиве

В случае если массив упорядочен (скажем, по возрастанию), линейный поиск неэффективен: действительно, сравнив “средний” элемент массива мы можем сразу отсечь половину значений.

Имеется упорядоченный по возрастанию массив \(a\) размера \(n\) (индексация с 1), найти индекс элемента равного \(P\)

Алгоритм:

Установить \(k:=1\), \(m:=n\)
Если \(m<k\), алгоритм завершён неудачно
\(p:=\floor{(n+k)/2}\)
Если \(a_p < P\), то \(k:=p+1\), если \(a_p > P\), то \(m:=p-1\); иначе, \(a_p=P\), вывести \(p\), алгоритм завершён удачно
перейти к шагу 2

Блок-схема алгоритма

Алгоритмы сортировки

Общая постановка: упорядочить произвольный массив \(n\) элементов по возрастанию (точнее, неубыванию). Полагается, что для элементов корректно определены операции \(<\), \(>\) и \(=\).

Простые сортировки

Сортировка “пузырьком”

Простейшая идея:

for m from n-1 to 1
  for j from 1 to m
    if a[j] > a[j+1]
      swap(a[j], a[j+1])
    end if
  end for j
end for m

Оптимизация: раннее завершение если массив не отсортирован

for m from n-1 to 1
  swapped = false
  for j from 1 to m
    if a[j] > a[j+1]
      swapped = true
      swap(a[j], a[j+1])
    end if
  end for j
  if swapped
    break
  end if
end for m

Сложность: в лучшем случае \(n-1\) операций сравнения (если массив отсортирован). В худшем случае \(n-1+n-2+n-3+\ldots = n(n-1)/2 = \mathcal O(n^2).\) Максимально \(n(n-1)/2 = \mathcal O(n^2).\) обменов.

Сортировка выбором

for i from 1 to n - 1
  min := i

  for j from i + 1 to n
     if a[j] < a[min]
        min := j
     end if
  end for j

  if indexMin ≠ i
     swap(a[min], a[i])
  end if
end for i

Сложность: \(n(n-1)/2 = \mathcal O(n^2)\) операций сравнения. Не более \(n-1 = \mathcal O(n)\) обменов.

Сортировка вставками

for i from 2 to n
    x := a[i]
    j := i
    while (j > 1 and a[j-1] > x)
        a[j] := a[j-1]
        j := j - 1
    end while
    a[j] := x
end for i

Сортировка вставками сортирует массив с начала. На каждой итерации алгоритм ищет подходящее место для вставки следующего элемента в уже отсортированную часть.

В приведённой реализации сложность по сравнениям \(1+2+\ldots+n-1 = n(n-1)/2 = \mathcal O(n^2)\), сложность по присваиваниям \(\mathcal O(n^2)\).

Если вместо массива использовать структуру данных, позволяющую \(\mathcal O(1)\) вставку (например, список), сложность по присваиваниям можно улучшить до \(\mathcal O(n)\). Если использовать бинарный поиск в отсортированной части, сложность по сравнениям можно улучшить до \(\mathcal O(n\log n)\). Увы, скомбинировать эти подходы не получится: для эффективного бинарного поиска необходим случайный доступ к элементам, что не поддерживается структурами данных с эффективной (\(\mathcal O(1)\)) вставкой.

Сортировка слиянием

algorithm merge_sort(a[n])
  if n ≤ 1
    return a

  mid := n/2

  left := merge_sort(a[1..mid])
  right := merge_sort(a[mid+1..n])

  return merge(left, right)
end algorithm merge_sort

algorithm merge(a[n], b[m])
  result := new array[n+m]
  i := 1
  j := 1
  k := 1
  while (i ≤ n and j ≤ m)
    if a[i] < b[j]
      result[k] := a[i]
      i := i+1
    else
      result[k] := b[j]
      j := j+1
    end if
    k := k+1
  end while
  while (i ≤ n)
    result[k] := a[i]
    k := k+1
    i := i+1
  end while
  while (j ≤ m)
    result[k] := b[j]
    k := k+1
    j := j+1
  end while
  return result
end algorithm merge

Используется метод “разделяй и властвуй”: массив разбивается пополам, каждая из частей рекурсивно сортируется, затем отсортированные части объединяются.

Рекурсия очевидно имеет конечную глубину, т.к. массив 1 элемента тривиально отсортирован.

Оценим сложность вычислений. Пусть сортировка массива размера \(n\) имеет сложность \(t(n)\). На каждом уровне рекурсии тогда требуется \(2t(n/2)+q(n),\) где \(q(n)\) – сложность объединения merge. \(q(n) = \mathcal O(n) = c\cdot n\). Тогда имеем

\[t(n) = 2t(n/2)+c\cdot n\] \[t(1) = \mathcal O(1) = c\]

Тогда

\[t(n) = 2(2t(n/2^2)+c\cdot n/2)+c\cdot n = 2^2 t(n/2^2)+2c\cdot n\] \[t(n) = 2^2 (2t(n/2^3)+c\cdot n/4)+2c\cdot n = 2^3t(n/2^3)+3c\cdot n\] \[\ldots\] \[t(n) = c 2^{\log_2 n} + c\cdot n \log_2 n = c n + c\cdot n\log_2 n = \mathcal O(n\log n)\]

Можно показать (сделаем это позже), что сортировка, основанная на бинарном сравнении, не может иметь сложность ниже \(\mathcal O(n\log n).\)

Сортировка подсчётом

Возможно ли производить сортировку быстрее, чем за \(\mathcal O(n\log n)\)?

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

Простейший вариант сортировки, не использующей напрямую операцию сравнения является сортировка подсчётом.

Рассмотрим некоторый массив целых чисел \(\brace{x_i},\) причём \(0 \le x_i < \overline x.\)

Построим на основе массива \(\brace{x_i}\) новый массив \(\brace{c_j},\) где \(c_j\) – число элементов \(\brace{x_i},\) равных \(j\): \[c_j = \underset{\brace{x_i}}{\mathrm{count}}(j)\]

Сложность построения \(\brace{c_j}\) составляет \(\mathcal O(N),\) где \(N\) – размер \(\brace{x_i}.\)

На основе \(\brace{c_j}\) несложно построить отсортированную последовательность \(\brace{x_k}\), для каждого \(j\) просто добавив в \(\brace{x_k}\) \(c_j\) элементов равных \(j\). Сложность этого построения \(\mathcal O(\overline x).\)

Тогда сложность всего алгоритма – \(\mathcal O(N+\overline x),\) или \(\mathcal O(N)\) если \(\overline x\) – константа.

Этот алгоритм, понятно, применим только если \(\overline x\) сравнительно мало. Действительно, пространственная сложность алгоритма \(\mathcal O(\overline x),\) и, скажем, при \(\overline x = 2^{64},\) потребуется по меньшей мере 18 эксабайт (18·10¹⁸ байт, 18 млн терабайт) дополнительной памяти.

Поразрядная сортировка (radix sort)

Поразрядная сортировка основана на сортировке подсчётом и том факте, что для сортировки чисел, представленных в \(P\)-ичной системе счисления, достаточно последовательно отсортировать числа по каждому разряду. Это позволяет применить сортировку подсчётом к каждому разряду. Тогда для некоторого \(P,\) сложность поразрядной сортировки составит примерно \(\mathcal O(N\log_P \overline x)=\mathcal O(N).\)

Рассмотрим алгоритм более подробно. Пусть K – число \(P\)-ичных разрядов в числе.

algorithm radix_sort(a[N])
  for r from 1 to K
    for j from 1 to P-1
      c[j] := 0
    end for i
    for i from 1 to N
      x := r-тый разряд a[i]
      c[x] := c[x] + 1
    end for i
    for j from 1 to P-1
      c[j] := c[j-1] + c[j]
    end for i
    for i from N to 1
      x := r-тый разряд a[i]
      c[x] := c[x] - 1
      b[c[x]] := a[i]
    end for i
    a := b
  end for r
end algorithm radix_sort

Сложность алгоритма таким образом \(\mathcal O(K\cdot(P+N)) = \mathcal O((P+N)\ceil{\log_P \overline x}).\) Положив \(\overline x\) и \(P\) константными, получаем сложность \(\mathcal O(N)\), однако понятно, что использование алгоритма осмысленно только если \(N\gg P\) и \(\ceil{\log_P \overline x}\) не слишком велико (т.е. \(\overline x \ll N\)).

Отметим также что алгоритм требует \(\mathcal O(N+P)\) дополнительной памяти.

Часто в качестве \(P\) выбирается степень двойки, например \(2^8\), \(2^{16}\), в основном в силу того, что получение разряда числа в таком случае сводится к битовым операциям.

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

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

Классы сложности алгоритмов

Примеры алгоритмов

Возведение в целую степень

Умножение целых

Пример

Алгоритмы поиска

Линейный поиск

Поиск минимального элемента

Бинарный поиск в упорядоченном массиве

Алгоритмы сортировки

Простые сортировки

Сортировка “пузырьком”

Сортировка выбором

Сортировка вставками

Сортировка слиянием

Сортировка подсчётом

Поразрядная сортировка (radix sort)