Времени работы алгоритма tmin n соответствует

Рассматривая
различные алгоритмы решения одной и
той же задачи, по­лезно проанализировать,
сколько вычислительных ресурсов они
требуют (время работы, память), и выбрать
наиболее эффективный. Конечно, надо
договориться о том, какая модель
вычислений используется. В данном
учебном пособии в качестве модели по
большей части используется обычная
однопроцессорная машина
с произвольным доступом
(random—access
machine,
RAM),
не предусматривающая параллельного
выполнения операций.

Под
временем
работы
(running
time)
алгоритма будем подразумевать число
элементар­ных шагов, которые он
выполняет. Положим, что одна строка
псевдокода требует не более чем
фиксированного числа операций (если
только это не словесное описание каких-то
сложных действий – типа «отсортировать
все точки по x-координате»).
Следует также различать вызов
(call)
процедуры (на который уходит фиксированное
число операций) и её исполнение
(execution),
которое может быть долгим.

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

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

1. Временная
   сложность алгоритма программы;

2. Качество
   скомпилированного кода исполняемой
   программы;

3. Машинные
   инструкции, используемые для выполнения
   программы.

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

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

O-символики.

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

Листинг
1.3 – Псевдокод алгоритма сортировки
вставками с оценками времени выполнения

Для
вычисления суммарного времени выполнения
процедуры Insertion-Sort
отметим
около каждой стро­ки её стоимость
(число операций) и число раз, которое
эта строка исполняется. Для каждого j
от
2 до п
(здесь
п
=
length[A]
–
размер массива) требуется подсчитать,
сколько раз будет исполнена строка 5,
обозначим это число через t_j.
Строки
внутри цикла выполняются на один раз
меньше, чем проверка, поскольку последняя
проверка выводит из цикла. Строка
стоимостью c,
повторённая т
раз,
даёт вклад c
m
в
общее число операций (однако, это
выражение нельзя использовать для
оценки количества использованной
памяти). Сложив вклады всех строк, получим

Время
работы процедуры зависит не только от
п
но
и от того, какой именно массив размера
п
подан
ей на вход. Для процедуры Insertion-Sort
наиболее
благоприятен случай, когда массив уже
отсортиро­ван. Тогда цикл в строке 5
завершается после первой же проверки
(поскольку A[i]
≤
key
при
i
=
j
–
1), так что все t_j
равны
1, и общее время есть

Таким
образом, в наиболее благоприятном случае
время T(n),
необходимое для сортировки массива
размера п,
является
линейной функцией (linear
function)
от n,
т.е. имеет вид Т(п)
=
a  n + b
для некоторых констант a
и
b.
Эти константы определяются выбранными
значениями с₁,…,
с₈.

Если же массив
расположен в обратном (убывающем)
порядке, время работы

процедуры
будет максимальным: каждый элемент A[j]
придётся
сравнить со всеми элементами А[1],…,
A[j
–
1]. При этом t_j
= j.
Поскольку

получаем, что в
худшем случае время работы процедуры
равно

В
данном
случае
T(n)
– квадратичная
(quadratic
function),
т.е.
имеет
вид
Т(п) = an²
+ bn
+ с.
Константы
a, b и
с здесь
также определяются значениями с₁,…,с₈.

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

Например,
если число тактов (действий), необходимое
для работы алгоритма, выражается как
16n² + 12n log n + 2n + 3,
то это алгоритм, для которого T(n)
имеет порядок O(n²).
При формировании асимптотической
O-оценки
из всех слагаемых исходного выражения
оставляется одно, вносящее наибольший
вклад при больших n
(остальными слагаемыми можно пренебречь)
и игнорируется коэффициент перед ним
(так как все асимптотические оценки
даются с точностью до константы).

Когда
используют обозначение O(),
имеют в виду не точное время исполнения,
а только его предел сверху, причем с
точностью до постоянного множителя.
Когда говорят, например, что алгоритму
требуется время порядка O(n²),
имеют в виду, что время исполнения задачи
растет не быстрее, чем квадрат количества
элементов.

Таблица 1.2
– Сравнительный анализ скорости роста
функций

Рисунок
1.1 – Примеры различных функциональных
зависимостей

Если
считать, что числа, приведенные в
таблице 1.2,
соответствуют микросекундам, то для
задачи с 1048476 элементами алгоритму со
временем работы T(log n)
потребуется 20 микросекунд, а алгоритму
со временем работы T(n²)
– более 12 дней.

Если
операция выполняется за фиксированное
число шагов, не зависящее от количества
данных, то принято писать O(1).

Следует
обратить внимание, что основание
логарифма в асимптотических оценках
не пишется. Причина этого весьма проста.
Пусть есть O(log₂ n).
Но log₂ n = log₃ n / log₃ 2,
а log₃ 2,
как и любую константу, символ О()
не учитывает. Таким образом, O(log₂ n)
= O(log₃ n).
К любому основанию можно перейти
аналогично, а, значит, и писать его не
имеет смысла.

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

• максимальную
  сложность T_max(n),
  или сложность наиболее неблагоприятного
  случая, когда алгоритм работает дольше
  всего;

• среднюю
  сложность T_mid(n)
  – сложность алгоритма в среднем;

• минимальную
  сложность T_min(n)
  – сложность в наиболее благоприятном
  случае, когда алгоритм справляется
  быстрее всего.

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

1. Время
   выполнения операций присваивания,
   чтения, записи обычно имеют порядок
   O(1).
   Исключением являются операторы
   присваивания, в которых операнды
   представляют собой массивы или вызовы
   функций;

2. Время
   выполнения последовательности операций
   совпадает с наибольшим временем
   выполнения операции в данной
   последовательности (правило сумм: если
   T₁(n)
   имеет порядок O(f(n)),
   а T₂(n)
   – порядок O(g(n)),
   то T₁(n)
   + T₂(n)
   имеет порядок O(max(f(n),
   g(n)));

3. Время
   выполнения конструкции ветвления
   (if-then-else)
   состоит из времени вычисления логического
   выражения (обычно имеет порядок O(1))
   и наибольшего из времени, необходимого
   для выполнения операций, исполняемых
   при истинном значении логического
   выражения и при ложном значении
   логического выражения;

4. Время
   выполнения цикла состоит из времени
   вычисления условия прекращения цикла
   (обычно имеет порядок O(1) )
   и произведения количества выполненных
   итераций цикла на наибольшее возможное
   время выполнения операций тела цикла.

5. Время
   выполнения операции вызова процедур
   определяется как время выполнения
   вызываемой процедуры;

6. При
   наличии в алгоритме операции безусловного
   перехода, необходимо учитывать изменения
   последовательности операций,
   осуществляемых с использованием этих
   операции безусловного перехода.

Итак,
время работы в худшем случае и в лучшем
случае могут
сильно
различаться. При анализе алгоритмов
наиболее часто используется время
работы в худшем случае
(worst—case
running
time),
которое определяется как максимальное
время работы для входов данного размера.
Почему? Вот несколько причин.

1. Зная
   время работы в худшем случае можно
   гарантировать, что выполнение
   алгоритма
   закончится за некоторое время при любом
   входе данного размера;

2. На
   практике «плохие» входы (для которых
   время работы близко к максимуму)
   встречаются наиболее часто. Например,
   для базы данных плохим запросом может
   быть поиск отсутствующего элемента
   (очень распространенная ситуация);

3. Время
   работы в среднем может быть до­вольно
   близко к времени работы в худшем случае.
   Пусть, например, сортируется массив
   из п
   случайных
   чисел
   с помощью процедуры Insertion-Sort.Сколько
   раз придётся выполнить цикл в строках
   5-8 (листинг 1.3)? В среднем около половины
   элементов массива A[1..j
   – 1]
   больше A[j],
   так
   что t_j
   в
   среднем можно считать равным j/2,
   и
   время Т(п)
   квадратично
   зависит от n.

В
некоторых случаях требуется также
среднее время
работы
(average—case
running
time,
expected
running
time)
алгоритма на входах данной длины.
Конечно, эта величина зависит от
выбранного распределения вероятно­стей,
и на практике реальное распределение
входов может отличаться от пред­полагаемого,
которое обычно считают равномерным.
Иногда можно добиться равномерности
распределения, используя датчик случайных
чисел.

В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные ^[1]. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения работы, для всех входов длины n не превосходит 5n³ + 3n для некоторого n (большего некоторого n₀), асимптотическая временная сложность равна O (n³).

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

Поскольку производительность алгоритма может отличаться при входах одного и того же размера, обычно используется временная сложность наихудшего случая^[en] поведения алгоритма, которая обозначается как T(n) и которая определяется как максимальное время, которое требуется для любого входа длины n. Реже, и это обычно оговаривается специально, время измеряется как средняя сложность^[en]. Сложность по времени классифицируется природой функции T(n). Например, алгоритм с T(n) = O(n) называется алгоритмом линейного времени, а об алгоритме с T(n) = O(Mⁿ) и mⁿ= O(T(n)) для некоторого M ≥ m > 1 говорят как об алгоритме с экспоненциальным временем.

Таблица сложностей по времени

Следующая таблица суммирует некоторые, обычно рассматриваемые, классы сложности. В таблице poly(x) = x^O(1), т.е. многочлен от x.

Постоянное время

Говорят, что алгоритм является алгоритмом постоянного времени (записывается как время O(1)), если значение T(n) ограничено значением, не зависящим от размера входа. Например, получение одного элемента в массиве занимает постоянное время, поскольку выполняется единственная команда для его обнаружения. Однако нахождение минимального значения в несортированном массиве не является операцией с постоянным временем, поскольку мы должны просмотреть каждый элемент массива. Таким образом, эта операция занимает линейное время, O(n). Если число элементов известно заранее и не меняется, о таком алгоритме можно говорить как об алгоритме постоянного времени.

Несмотря на название «постоянное время», время работы не обязательно должно быть независимым от размеров задачи, но верхняя граница времени работы не должна зависеть. Например, задача «обменять значения a и b, если необходимо, чтобы в результате получили a≤b«, считается задачей постоянного времени, хотя время работы алгоритма может зависеть от того, выполняется ли уже неравенство a ≤ b или нет. Однако существует некая константа t, для которой время выполнения задачи всегда не превосходит t.

Ниже приведены некоторые примеры кода, работающие за постоянное время:

int index = 5;
int item = list[index];
if (условие верно) then
   выполнить некоторые операции с постоянным временем работы
else
   выполнить некоторые операции с постоянным временем работы
for i = 1 to 100
   for j = 1 to 200
      выполнить некоторые операции с постоянным временем работы

Если T(n) равен O(некоторое постоянное значение), это эквивалентно T(n) равно O(1).

Логарифмическое время

Говорят, что алгоритм выполняется за логарифмическое время, если T(n) = O(log n). Поскольку в компьютерах принята двоичная система счисления, в качестве базы логарифма используется 2 (то есть, log₂ n). Однако при замене базы^[en] логарифмы log_a n и log_b n отличаются лишь на постоянный множитель, который в записи O-большое отбрасывается. Таким образом, O(log n) является стандартной записью для алгоритмов логарифмического времени независимо от базы логарифма.

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

O(log n) алгоритмы считаются высокоэффективными, поскольку время выполнения операции в пересчёте на один элемент уменьшается с увеличением числа элементов.

Очень простой пример такого алгоритма — деление строки пополам, вторая половина опять делится пополам, и так далее. Это занимает время O(log n) (где n — длина строки, мы здесь полагаем, что console.log и str.substring занимают постоянное время).
Это означает, что для увеличения числа печатей необходимо удвоить длину строки.

// Функция для рекурсивной печати правой половины строки
var right = function(str)
{
    var length = str.length;
    
    // вспомогательная функция
    var help = function(index)
    {
       // Рекурсия: печатаем правую половину
        if(index < length)
        {
          
            // Печатаем символы от index до конца строки
            console.log(str.substring(index, length));
            
            // рекурсивный вызов: вызываем вспомогательную функцию с правой частью
            help(Math.ceil((length + index)/2));
        }
    }
    help(0);
}

Полилогарифмическое время

Говорят, что алгоритм выполняется за полилогарифмическое время, если T(n) = O((log n)^k), для некоторого k. Например, задача о порядке перемножения матриц может быть решена за полилогарифмическое время на параллельной РАМ-машине^[en][4].

Сублинейное время

Говорят, что алгоритм выполняется за сублинейное время, если T(n) = o(n). В частности, сюда включаются алгоритмы с временной сложностью, перечисленные выше, как и другие, например, поиск Гровера со сложностью O(n^½).

Типичные алгоритмы, которые, являясь точными, всё же работают за сублинейное время, используют распараллеливание процессов (как это делают алгоритм NC₁ вычисления определителя матрицы), неклассические вычисления (как в поиске Гровера) или имеют гарантированное предположение о струтуре входа (как работающие за логарифмическое время, алгоритмы двоичного поиска и многие алгоритмы обработки деревьев). Однако формальные конструкции, такие как множество всех строк, имеющие бит 1 в позиции, определяемой первыми log(n) битами строки, могут зависеть от каждого бита входа, но, всё же, оставаться сублинейными по времени.

Термин алгоритм с сублинейным временем работы обычно используется для алгоритмов, которые, в отличие от приведённых выше примеров, работают на обычных последовательных моделях машин и не предполагают априорных знаний о структуре входа ^[5]. Однако для них допускается применение вероятностных методов и даже более того, алгоритмы должны быть вероятностными для большинства тривиальных задач.

Поскольку такой алгоритм обязан давать ответ без полного чтения входных данных, он в очень сильной степени зависит от способов доступа, разрешённых во входном потоке. Обычно для потока, представляющего собой битовую строку b₁,…,b_k, предполагается, что алгоритм может за время O(1) запросить значение b_i для любого i.

Алгоритмы сублинейного времени, как правило, вероятностны и дают лишь аппроксимированное решение. Алгоритмы сублинейного времени выполнения возникают естественным образом при исследовании проверки свойств^[en].

Линейное время

Говорят, что алгоритм работает за линейное время, или O(n), если его сложность равна O(n). Неформально, это означает, что для достаточно большого размера входных данных время работы увеличивается линейно от размера входа. Например, процедура, суммирующая все элементы списка, требует время, пропорциональное длине списка. Это описание не вполне точно, поскольку время работы может существенно отличаться от точной пропорциональности, особенно для малых значений n.

Линейное время часто рассматривается как желательный атрибут алгоритма^[6]. Было проведено много исследований для создания алгоритмов с (почти) линейным временем работы или лучшим. Эти исследования включали как программные, так и аппаратные подходы. В случае аппаратного исполнения некоторые алгоритмы, которые, с математической точки зрения, никогда не могут достичь линейного времени исполнения в стандартных моделях вычислений, могут работать за линейное время. Существуют некоторые аппаратные технологии, которые используют параллельность для достижения такой цели. Примером служит ассоциативная память. Эта концепция линейного времени используется в алгоритмах сравнения строк, таких как алгоритм Бойера — Мура и алгоритм Укконена.

Квазилинейное время

Говорят, что алгоритм работает за квазилинейное время, если T(n) = O(n log^k n) для некоторой константы k. Линейно-логарифмическое время является частным случаем с k = 1^[7]. При использовании обозначения слабое-O эти алгоритмы являются Õ(n). Алгоритмы квазилинейного времени являются также o(n^1+ε) для любого ε > 0 и работают быстрее любого полинома от n со степенью, строго большей 1.

Алгоритмы, работающие за квазилинейное время, вдобавок к линейно-логарифмическим алгоритмам, упомянутым выше, включают:

• Сортировка слиянием на месте, O(n log² n)
• Быстрая сортировка, O(n log n), в вероятностной версии имеет линейно-логарифмическое время выполнения в худшем случае. Невероятностная версия имеет линейно-логарифмическое время работы только для измерения сложности в среднем.
• Пирамидальная сортировка, O(n log n), сортировка слиянием, introsort, бинарная сортировка с помощью дерева, плавная сортировка, пасьянсная сортировка^[en], и т.д. в худшем случае
• Быстрые преобразования Фурье, O(n log n)
• Вычисление матриц Монжа, O(n log n)

Линейно-логарифмическое время

Линейно-логарифмическое является частным случаем квазилинейного времени с показателем k = 1 на логарифмическом члене.

Линейно-логарифмическая функция — это функция вида n • log n (т.е. произведение линейного^[en] и логарифмического членов). Говорят, что алгоритм работает за линейно-логарифмическое время, если T(n) = O(n log n).^[8] Таким образом, линейно-логарифмический элемент растёт быстрее, чем линейный член, но медленнее, чем любой многочлен от n со степенью, строго большей 1.

Во многих случаях время работы n • log n является просто результатом выполнения операции Θ(log n) n раз. Например, сортировка с помощью двоичного дерева создаёт двоичное дерево путём вставки каждого элемента в массив размером n один за другим. Поскольку операция вставки в сбалансированное бинарное дерево поиска^[en] занимает время O(log n), общее время выполнения алгоритма будет линейно-логарифмическим.

Сортировки сравнением^[en] требуют по меньшей мере линейно-логарифмического числа сравнений для наихудшего случая, поскольку log(n!) = Θ(n log n) по формуле Стирлинга. То же время выполнения зачастую возникает из рекуррентного уравнения T(n) = 2 T(n/2) + O(n).

Подквадратичное время

Говорят, что алгоритм выполняется за субквадратичное время, если T(n) = o(n²).

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

Полиномиальное время

Говорят, что алгоритм работает за полиномиальное время, если время работы ограничено сверху^[en] многочленом от размера входа для алгоритма, то есть T(n) = O(n^k) для некоторой константы k^[1][9]. Задачи, для которых алгоритмы с детерминированным полиномиальным временем существуют, принадлежат классу сложности P, который является центральным в теории вычислительной сложности. Тезис Кобэма^[en] утверждает, что полиномиальное время является синонимом понятий «легко поддающийся обработке», «выполнимый», «эффективный» или «быстрый»^[10].

Некоторые примеры алгоритмов полиномиального времени:

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

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

Строго полиномиальное время определяется в арифметической модели вычислений. В этой модели базовые арифметические операции (сложение, вычитание, умножение, деление и сравнение) берутся за единицы выполнения, независимо от длины операндов. Алгоритм работает в строго полиномиальное время, если^[11]

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

Любой алгоритм с этими двумя свойствами можно привести к алгоритму полиномиального времени путём замены арифметических операций на соответствующие алгоритмы выполнения арифметических операций на машине Тьюринга. Если второе из вышеприведённых требований не выполняется, это больше не будет верно. Если задано целое число (которое занимает память, пропорциональную n в машине Тьюринга), можно вычислить с помощью n операций, используя повторное возведение в степень. Однако память, используемая для представления , пропорциональна , и она скорее экспоненционально, чем полиномиально, зависит от памяти, используемой для входа. Отсюда — невозможно выполнить эти вычисления за полиномиальное время на машине Тьюринга, но можно выполнить за полиномиальное число арифметических операций.

Обратно — существуют алгоритмы, которые работают за число шагов машины Тьюринга, ограниченных полиномиальной длиной бинарно закодированного входа, но не работают за число арифметических операций, ограниченное многочленом от количества чисел на входе. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Для двух целых чисел и время работы алгоритма ограничено шагам машины Тьюринга. Это число является многочленом от размера бинарного представления чисел и , что грубо можно представить как . В то же самое время число арифметических операций нельзя ограничить числом целых во входе (что в данном случае является константой — имеется только два числа во входе). Ввиду этого замечания алгоритм не работает в строго полиномиальное время. Реальное время работы алгоритма зависит от величин и , а не только от числа целых чисел во входе.

Если алгоритм работает за полиномиальное время, но не за строго полиномиальное время, говорят, что он работает за слабо полиномиальное время^[12].
Хорошо известным примером задачи, для которой известен слабо полиномиальный алгоритм, но не известен строго полиномиальный алгоритм, является линейное программирование. Слабо полиномиальное время не следует путать с псевдополиномиальным временем.

Классы сложности

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

• P: Класс сложности задач разрешимости, которые могут быть решены в детерминированной машине Тьюринга за полиномиальное время.
• NP: Класс сложности задач разрешимости, которые могут быть решены в недетерминированной машине Тьюринга за полиномиальное время.
• ZPP: Класс сложности задач разрешимости, которые могут быть решены с нулевой ошибкой в вероятностной машине Тьюринга за полиномиальное время.
• RP: Класс сложности задач разрешимости, которые могут быть решены с односторонними ошибками в вероятностной машине Тьюринга за полиномиальное время.
• BPP: Класс сложности задач разрешимости, которые могут быть решены с двусторонними ошибками в вероятностной машине Тьюринга за полиномиальное время.
• BQP: Класс сложности задач разрешимости, которые могут быть решены с двусторонними ошибками в квантовой машине Тьюринга за полиномиальное время.

P является наименьшим классом временной сложности на детерминированной машине, которая является устойчивой^[en] в терминах изменения модели машины. (Например, переход от одноленточной машины Тьюринга к мультиленточной может привести к квадратичному ускорению, но любой алгоритм, работающий за полиномиальное время на одной модели, будет работать за полиномиальное время на другой.)

Суперполиномиальное время

Говорят, что алгоритм работает за суперполиномиальное время, если T(n) не ограничен сверху полиномом. Это время равно ω(n^c) для всех констант c, где n — входной параметр, обычно — число бит входа.

Например, алгоритм, осуществляющий 2ⁿ шагов, для входа размера n требует суперполиномиального времени (конкретнее, экспоненциального времени).

Ясно, что алгоритм, использующий экспоненциальные ресурсы, суперполиномиален, но некоторые алгоритмы очень слабо суперполиномиальны. Например, тест простоты Адлемана — Померанса — Румели^[en]* работает за время n^{O(log log n)} на n-битном входе. Это растёт быстрее, чем любой полином, для достаточно большого n, но размер входа должен стать очень большим, чтобы он не доминировался полиномом малой степени.

Алгоритм, требующий суперполиномиального времени, лежит вне класса сложности P. Тезис Кобэма^[en] утверждает, что эти алгоритмы непрактичны, и во многих случаях это так. Поскольку задача равенства классов P и NP не решена, никаких алгоритмов для решения NP-полных задач за полиномиальное время в настоящее время не известно.

Квазиполиномиальное время

Алгоритмы квазиполиномиального времени — это алгоритмы, работающие медленнее, чем за полиномиальное время, но не столь медленно, как алгоритмы экспоненциального времени. Время работы в худшем случае для квазиполиномиального алгоритма равно для некоторого фиксированного c. Хорошо известный классический алгоритм разложения целого числа на множители, общий метод решета числового поля, который работает за время около , не является квазиполиномиальным, поскольку время работы нельзя представить как для некоторого фиксированного c. Если константа «c» в определении алгоритма квазиполиномиального времени равна 1, мы получаем алгоритм полиномиального времени, а если она меньше 1, мы получаем алгоритм сублинейного времени.

Алгоритмы квазиполиномиального времени обычно возникают при сведении NP-трудной задачи к другой задаче. Например, можно взять NP-трудную задачу, скажем, 3SAT, и свести её к другой задаче B, но размер задачи станет равным . В этом случае сведение не доказывает, что задача B NP-трудна, такое сведение лишь показывает, что не существует полиномиального алгоритма для B, если только не существует квазиполиномиального алгоритма для 3SAT (а тогда и для всех NP-задач). Подобным образом — существуют некоторые задачи, для которых мы знаем алгоритмы с квазиполиномиальным временем, но для которых алгоритмы с полиномиальным временем неизвестны. Такие задачи появляются в аппроксимационых алгоритмах. Знаменитый пример — ориентированная задача Штайнера, для которой существует аппроксимационный квазиполиномиальный алгоритм с аппроксимационным коэффициентом (где n — число вершин), но существование алгоритма с полиномиальным временем является открытой проблемой.

Класс сложности QP состоит из всех задач, имеющих алгоритмы квазиполиномиального времени. Его можно определить в терминах DTIME следующим образом^[13]

Связь с NP-полными задачами

В теории сложности нерешённая проблема равенства классов P и NP спрашивает, не имеют ли все задачи из класса NP алгоритмы решения за полиномиальное время. Все хорошо известные алгоритмы для NP-полных задач, наподобие 3SAT, имеют экспоненциальное время. Более того, существует гипотеза, что для многих естественных NP-полных задач не существует алгоритмов с субэкспоненциальным временем выполнения. Здесь «субэкспоненциальное время » взято в смысле второго определения, приведённого ниже. (С другой стороны, многие задачи из теории графов, представленные естественным путём матрицами смежности, разрешимы за субэкспоненциальное время просто потому, что размер входа равен квадрату числа вершин.) Эта гипотеза (для задачи k-SAT) известна как гипотеза экспоненциального времени^[en][14]. Поскольку она предполагает, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени, некоторые результаты неаппроксимируемости в области аппроксимационных алгоритмов исходят из того, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени. Например, смотрите известные результаты по неаппроксимируемости задачи о покрытии множества.

Субэкспоненциальное время

Термин субэкспоненциальное^[en] время используется, чтобы выразить, что время выполнения некоторого алгоритма может расти быстрее любого полиномиального, но остаётся существенно меньше, чем экспоненциальное. В этом смысле задачи, имеющие алгоритмы субэкспоненциального времени, являются более податливыми, чем алгоритмы только с экспотенциальным временем. Точное определение «субэкспоненциальный» пока не является общепринятым^[15], и мы приводим ниже два наиболее распространённых определения.

Первое определение

Говорят, что задача решается за субэкспоненциальное время, если она решается алгоритмом, логарифм времени работы которого растёт меньше, чем любой заданный многочлен. Более точно — задача имеет субэкспоненциальное время, если для любого ε > 0 существует алгоритм, который решает задачу за время O(2^nε). Множество все таких задач составляет класс сложности SUBEXP, который в терминах DTIME можно выразить как^{[3][16][17][18]}.

Заметим, что здесь ε не является частью входных данных и для каждого ε может существовать свой собственный алгоритм решения задачи.

Второе определение

Некоторые авторы определяют субэкспоненциальное время как время работы 2^{o(n)[14][19][20]}. Это определение допускает большее время работы, чем первое определение. Примером такого алгоритма субэкспоненциального времени служит хорошо известный классический алгоритм разложения целых чисел на множители, общий метод решета числового поля, который работает за время около , где длина входа равна n. Другим примером служит хорошо известный алгоритм для задачи изоморфизма графов^[en], время работы которого равно .

Заметим, что есть разница, является ли алгоритм субэкспоненциальным по числу вершин или числу рёбер. В параметризованной сложности^[en] эта разница присутствует явно путём указания пары , задачи разрешимости и параметра k. SUBEPT является классом всех параметризованных задач, которые работают за субэкспоненциальное время по k и за полиномиальное по n^[21]:

Точнее, SUBEPT является классом всех параметризованных задач , для которых существует вычислимая функция с и алгоритм, который решает L за время .

Гипотеза об экспоненциональном времени

Гипотеза об экспоненциональном времени (‘ETH) утверждает, что 3SAT, задача выполнимости булевых формул в конъюнктивной нормальной форме с максимум тремя литералами на предложение и n переменными, не может быть решена за время 2^o(n). Точнее, гипотеза говорит, что существует некая константа c>0, такая, что 3SAT не может быть решена за время 2^cn на любой детерминированной машине Тьюринга. Если через m обозначить число предложений, ETH эквивалентна гипотезе, что k-SAT не может быть решена за время 2^o(m) для любого целого k ≥ 3^[22]. Из гипотезы об экспоненциальном времени следует, что P ≠ NP.

Экспоненциальное время

Говорят, что алгоритм работает за экспоненциальное время, если T(n) ограничено сверху значением 2^poly(n), где poly(n) — некий многочлен от n. Более формально, алгоритм работает за экспоненциальное время, если T(n) ограничено O(2^nk) с некоторой константой k. Задачи, которые выполняются за экспоненциальное время на детерминированных машинах Тьюринга, образуют класс сложности EXP.

Иногда термин экспоненциальное время используется для алгоритмов, для которых T(n) = 2^O(n), где показатель является не более чем линейной функцией от n. Это приводит к классу сложности E^[en].

Двойное экспоненциональное время

Говорят, что алгоритм выполняется за дважды экспоненциональное^[en] время, если T(n) ограничено сверху значением 2^2poly(n), где poly(n) — некоторый многочлен от n. Такие алгоритмы принадлежат классу сложности 2-EXPTIME^[en].

К хорошо известным дважды экспоненциальным алгоритмам принадлежат:

• Процедура вычисления для арифметики Пресбургера
• Вычисление базиса Грёбнера (в худшем случае^[23])
• Элиминация кванторов в вещественно замкнутых полях^[en] требует как минимум дважды экспоненциальное время выполнения ^[24] и может быть выполнена за это время^[25].

Смотрите также

• L-нотация
• Сложность по памяти^[en]

Примечания