Как определить теоретическую сложность алгоритма
Перейти к содержимому

Как определить теоретическую сложность алгоритма

  • автор:

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

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

Для большинства алгоритмов время выполнения и количество памяти нельзя выразить одним числом. Чем больше элементов будет во входящем массиве, тем дольше будут выполняться поиск и сортировка.

Для описания эффективности алгоритмов придумали нотацию Big-O.

Постоянная сложность — О(1)

Самый эффективный алгоритм в теории работает за постоянное время и расходует постоянное количество памяти. Как ни увеличивай объем входящих данных, сложность алгоритма не повысится. Эффективность (или сложность) такого алгоритма называют константным и записывают как O(1).

Пример алгоритма с постоянной сложностью:

const getArrayElement = (arr, i) => arr[i]; 

На вход получаем массив arr и индекс i . Возвращаем элемент массива на позиции i .

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

Линейная сложность — O(n)

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

Хороший пример — линейный поиск:

const findArrayElement = (arr, x) => < for (let i = 0; i  arr.length; i++) < if (arr[i] === x) < return i; > > return -1; > 

Если поиск в массиве из 10 элементов занимает 5 секунд, то в массиве из 100 элементов мы будем искать 100 секунд. В 10 раз дольше.

Такую сложность (эффективность) называют линейной и записывают как О(n).

Но, заметь, что алгоритму линейного поиска не нужна дополнительная память. Поэтому, по этой характеристике он получает высший балл — O(1).

Квадратичная сложность — O(n^2^)

Простые алгоритмы сортировки, такие как сортировка пузырьком или сортировка выбором имеют сложность О(n^2^).

Это не очень эффективно. При росте длины массива в 10 раз, время выполнения алгоритма увеличится в 10^2^ (в 100) раз!

Так происходит из-за того, что в алгоритме используется вложенный цикл. Сложность одного прохода мы оцениваем как O(n). Но проходим мы его не один раз, а **n **раз. Поэтому и получается сложность O(n * n) = O(n^2^).

Логарифмическая сложность — O(log n)

Алгоритмы, которые на каждой итерации могут сократить количество анализируемых данных имеют логарифмическую сложность — O(log n).

В качестве примера можно представить двоичный поиск. На каждой итерации мы можем отбросить половину данных и работать только с оставшимися.

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

Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

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

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max);
end;
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.
Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do

end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=O(N^3). Следующий фрагмент имеет именно такую сложность:
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do

end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do

end;
procedure Both;
begin
Fast;
Slow;
end;

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

Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
Рассмотрим рекурсивную реализацию вычисления факториала:
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).

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

Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.
Рассмотрим такую процедуру:
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.

Объёмная сложность рекурсивных алгоритмов

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

Средний и наихудший случай

Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.
function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i <=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.

Общие функции оценки сложности

Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0 5. N
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и 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.

Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).

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

Примеры асимптотических функций
f(n) g(n)
2n 2 + 7n — 3 n 2
98n*ln(n) n*ln(n)
5n + 2 n
8 1
Ω – оценка для лучшего случая

Определение схоже с определением оценки для худшего случая, однако
f(n) = Ω(g(n)), если
0 < c*g(n) < f(n)

Ω(g(n)) определяет класс функций, которые растут не медленнее, чем функция g(n) с точностью до константного множителя.

Θ – оценка для среднего случая

Стоит лишь упомянуть, что в данном случае функция f(n) при n > n0 всюду находится между c1*g(n) и c2*g(n), где c – константный множитель.
Например, при f(n) = n 2 + n; g(n) = n 2 .

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

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

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

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

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

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

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

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

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

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

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

1) i

На 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!)).

Выводы

Изучение сложности алгоритмов довольно увлекательная задача. На данный момент анализ простейших алгоритмов входит в учебные планы технических специальностей (если быть точным, обобщённого направления «Информатика и вычислительная техника»), занимающихся информатикой и прикладной математикой в сфере IT.
На основе сложности выделяются разные классы задач: P, NP, NPC. Но это уже не проблема теории асимптотического анализа алгоритмов.

  • теория алгоритмов
  • оценка алгоритмов
  • алгоритмы
  • асимптотический анализ алгоритмов

Классы сложности алгоритмов и задач — Алгоритмы на графах

В обычной жизни мы называем задачу сложной, если ее трудно решить. Но для программистов это работает не так: у них сложность задачи определяется сложностью алгоритма, который ее решает. В этом уроке мы подробнее познакомимся с термином «сложность» и узнаем, как классифицировать задачи по этому признаку.

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

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

Такие эффективные процессоры справляются даже с непростыми задачами. Для примера вспомним алгоритм перемножения матриц размером в

. Сложность этого алгоритма высокая —

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

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

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

Возьмем для примера уже известную нам задачу о рюкзаке, которая решается перебором. Для

предметов она выполняется за время

Существуют ли более быстрые решения? В строгом смысле — нет:

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

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

Другими словами, с количеством предметов радикально меняется и скорость выполнения алгоритма. Чтобы собрать рюкзак из пятидесяти предметов, потребуется двадцать минут, а из ста предметов — сорок миллиардов лет.

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

На практике, различия в сложности алгоритмов не так существенны — важнее, в какую половину таблицы они попали. Вернемся к нашей таблице:

Большинство востребованных алгоритмов можно разбить на две большие группы или два больших класса:

  • Если задача решается алгоритмами из зеленой зоны, то она относится к классу сложности P — это сокращение от polynomial (полиномиальные, они же степенные)
  • Если задача решается алгоритмами из красной зоны, то она относится к классу сложности NP — это сокращение от nondeterministic polynomial (недетерминированные полиномиальные)

К классу P относятся задачи не только со степенными, но и с более быстрыми алгоритмами — логарифмическими, линейными и линейно-логарифмическими. Название класса не следует понимать буквально. Оно означает, что для решения задачи существует достаточно быстрый алгоритм — не хуже полиномиального.

Недетерминированные полиномиальные задачи

В наших уроках мы избегаем сложной математики. Это связано с тем, что программирование — инженерная деятельность. Чтобы писать программы, программист должен владеть определенными методами, но ему необязательно придумывать эти методы и доказывать их корректность.

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

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

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

От обычного компьютера машина Тьюринга отличается только по одному параметру — у нее неограниченный запас процессоров и неограниченная оперативная память.

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

Формальное определение гласит:

К классу NP относятся все задачи, которые можно решить за полиномиальное время на недетерменированной машине Тьюринга

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

Однако у NP-задач есть и менее абстрактная формулировка.

Задачи разрешимости

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

Но есть и другие задачи, например: «Совпадают ли две строки символов или является массив отсортированным?». У подобных задач только два варианта решения — «да» или «нет». Такие задачи называют задачами разрешимости.

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

Представим, у нас есть карта с городами и расстояниями между ними. Нам говорят, что коммивояжер может объехать все города и суммарный путь не превысит

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

Теперь представим, что нам не только выдали карту, но и показали конкретный маршрут. Сложно ли решить такую задачу? Совсем нет. Мы всего лишь должны проверить несколько фактов:

  • В маршрут входят все города
  • Города появляются не более одного раза
  • Сумма всех расстояний между городами не превышает

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

Таким образом, мы приходим к еще одному определению:

К классу NP относятся задачи, решение которых можно проверить за полиномиальное время на детерминированной машине Тьюринга — то есть на обычном компьютере

Это определение не такое абстрактное, как предыдущее. По крайней мере, для проверки задач не требуется вымышленная машина — достаточно обычного компьютера.

В обоих определениях есть одна странность — задачи класса P входят в класс NP. Это сбивает с толку. Мы хотели различать задачи и ввели классы сложности, а теперь выясняется, что простые задачи относятся и к сложным.

На самом деле, противоречия нет.

Первая причина в том, что как речь идет о худшем случае, как в задачах класса P. Если задача решается за полиномиальное время, то и проверка решения займет полиномиальное время, даже в худшем случае. Но есть еще и вторая причина.

Основная проблема теории алгоритмов

Удивительный факт: мы не знаем, различаются ли классы P и NP на самом деле. Для задачи о рюкзаке или о коммивояжере известны только медленные переборные алгоритмы. Еще никто не доказал, что более быстрых алгоритмов не существует.

Такие доказательства возможны. Например, даже в самом быстром алгоритме сортировки количество сравнений не может быть меньше

. Это значит, что в общем случае сортировка не может быть быстрее, чем

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

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

Впрочем, за последние 50 лет не появилось ни одного быстрого алгоритма для задач класса NP. Проблема равенства или не равенства классов P и NP важна настолько, что ее называют основной проблемой теории алгоритмов или одной из задач тысячелетия.

Дело даже не в том, что мы сможем быстро решать практические задачи. Оказывается, что существует класс задач, которые называют NP-полными. Если мы найдем быстрый алгоритм для любой из них, то сможем придумать быстрый алгоритм для любой NP-задачи. Разберемся, почему это так.

NP-полные задачи

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

Кажется, что сводить другу к другу можно именно похожие задачи, но это не всегда так. Выше мы уже обсуждали недетерминированные машины Тьюринга и их важность для доказательств. В 1971 году американскому математику Стивену Куку удалось доказать, что все задачи из класса NP можно свести к задаче о выполнимости, которая в научных кругах называется SAT (от английского satisfiability — выполнимость).

Представим, что у нас есть логическая формула. На языке JavaScript это формула состоит из:

  • Скобок
  • Логических переменных со значением true и false
  • Логических операторов:
  • && (И)
  • || (ИЛИ)
  • ! (НЕ)

Примером такой формулы служит a && b || !c .

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

эта формула будет выполняться. Задача решается методом перебора. Для выражения из

переменных необходимо перебрать

вариантов, то есть речь идет об экспоненциальном алгоритме.

Стивен Кук доказал, что мы можем свести к решению SAT любую программу для недетерминированной машины Тьюринга, которая работает за полиномиальное время. Это утверждение звучит немного абстрактно, но из него следует важный вывод. Если мы найдем быстрое решение для SAT, то найдем и решение для любой задачи из класса NP, включая задачу о рюкзаке и коммивояжере.

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

Если мы выясним, что классы P и NP эквивалентны, это будет хорошим подарком человечеству. Но нас ждут и негативные последствия. Дело в том, что вся криптография с открытым ключом построена на предположении, что некоторые NP-задачи сложны.

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

А из-за теоремы Кука это обязательно случится, если мы обнаружим полиномиальный алгоритм для любой NP-полной задачи. Учитывая количество открытых NP-полных задач, можно предположить, что вероятность такого события достаточно высока.

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

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

Выводы

Повторим ключевые мысли этого урока:

  • В теории алгоритмов быстрые алгоритмы называют простыми, а медленные — сложными
  • Сложными называют задачи, для которых не существует быстрого решения
  • Большинство задач относятся к одному из классов сложности — P или NP
  • Задачи из класса P решаются за полиномиальное время в худшем случае
  • Задачи из класса NP проверяются за полиномиальное время в худшем случае
  • До сих пор неизвестно, эквивалентны ли классы P и NP
  • Если они эквивалентны, мы сможем составлять оптимальные расписания и строить оптимальные маршруты, но лишимся асимметричных методов шифрования, на которых работает весь интернет

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

Наши выпускники работают в компаниях:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *