Сложность в определении размера и. Моя научная и околонаучная деятельность: Вычислительная сложность алгоритмов

Для сравнения алгоритмов принято использовать обобщенную характеристику, называемую эффективностью. Говорят, что алгоритм Л, эффективнее алгоритма А 2 , если алгоритм Л, выполняется за меньшее время и (или) требует меньше компьютерных ресурсов (оперативной памяти, дискового пространства, сетевого трафика и т.п.).

Эффективный алгоритм должен удовлетворять требованиям приемлемого времени исполнения и разумной ресурсоемкое™, о чем уже упоминалось в параграфе 1.1. Совокупность этих характеристик составляет понятие сложности алгоритма. При увеличении времени исполнения алгоритма и (или) задействованных ресурсов сложность возрастает. Таким образом, понятия эффективности и сложности являются обратными один относительно другого.

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

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

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

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

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

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

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

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

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

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

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

Пусть п - объем входных данных для некоторого алгоритма. Обозначим за Т(п) количество инструкций, выполняемых на идеализированном компьютере при исполнении алгоритма, причем оно определяется для «наихудшего случая», когда объем операций максимален.

Понятие «наихудшего случая» можно проиллюстрировать на примере. Пусть рассматривается алгоритм проверки наличия числового элемента в некотором множестве (массиве) чисел. Если это множество упорядочено по возрастанию, то, вообще говоря, нет смысла проверять элементы, расположенные после первого элемента, который больше искомого. В этом случае Т(п) п. Однако в наихудшем случае (для произвольного несортированного множества) придется просмотреть все элементы множества. Очевидно, здесь Т(п) = п.

Вообще говоря, Т(п) является некоторой функцией от объема входных данных п. Во многих случаях Т(п) выражается полиномиальной, степенной или логарифмической функцией от п.

Поведение величины Т(п) в зависимости от увеличения п называют асимптотической сложностью алгоритма. Говорят, что Т(п ) имеет порядок сложности 0(J(n)) (читается «О большое от/от п») для некоторого алгоритма, если существуют константа с и объем данных щ такие, что Уп > п 0 и имеет место неравенство Т(п ) с/(п).

Данный факт записывается как Т(п) = 0(J(n)) и означает, что для функции Т(п) существуют такая функция f(n) и константа с, для которых, начиная с некоторого п 0 , значение Т(п) не превосходит cf(n).

Функция f(n) представляет собой верхнюю границу значений функции Т(п). Пусть, например, Т(п) = 2п А + п 2 . Выбрав значения п 0 = 0 и с = 5, для любого п > п 0 имеем Т(п) = 2п А + п 2 Т(п) имеет порядок я 4 .

Функция Т(п ) связана с определенным алгоритмом, поэтому часто говорят, что порядок сложности 0(/(п)) имеет именно алгоритм.

Говорят, что Т(п) имеет нижнюю границу Q(g(n)) (читается «омега большое от g от /г»), если существуют константа с и объем данных п 0 такие, что /п и имеет место неравенство Т(п) > cg(n).

Данный факт записывается как Т(п) = Q(g(n)). Пусть, например, Т(п) = 2я 4 + п 2 . Выбрав значение с = 1, для любого п имеем Т{п) = 2я 4 + п 2 > сп А > следовательно, Т(п ) имеет нижнюю границу я 4 .

Нетрудно видеть, что порядок и нижняя граница не являются единственными для некоторой функции Т(п). В примерах выше в качестве /(я) можно было выбрать я 5 , я 6 ,..., а в качестве g(n) - я 3 , я 2 ,.... Обычно в качестве /(я) выбирают функцию с минимальной степенью, а в качестве g(n) - с максимальной.

Порядок сложности 0(/(я)) и нижняя граница Q(g(rc)) представляют собой классы функций. Интуитивно Q(g"(n)) можно понимать как класс функций растущих по крайней мере так же быстро, как и Т(п). Аналогично, интуитивно 0(f(n)) можно понимать как класс функций, растущих не быстрее, чем Т(п). С практической точки зрения при оценке сложности алгоритма наиболее важным оказывается именно класс функций 0(f(n)). Определение вида функции /(я) и является основной задачей расчета теоретической сложности алгоритма.

Для любого алгоритма при определении степени роста можно воспользоваться следующими свойствами 0(/(я)):

1) 0(kf(ji)) = 0(/(я)), где k = const. Таким образом, постоянный множитель в функции не оказывает влияние на скорость роста. Например,

2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)). Таким образом, порядок произведения двух функций равен произведению их сложностей. Например,

Иногда это свойство записывают как

3) 0(/(п) + g(n)) равен доминанте (функции с максимальной степенью) функций /(я) и g(n). Например,

В теории сложности алгоритмов выделяют следующие классы функций сложности:

• 1) константная сложность 0(1). Время работы алгоритма и используемые ресурсы не имеют зависимости от объема входных данных. Обычно такую сложность имеют алгоритмы, не содержащие циклов и рекурсивных вызовов;
• 2) линейная сложность 0(п). Обычно такую сложность имеют задачи, в которых каждый элемент входных данных должен быть обработан определенное количество раз, никак не связанное с количеством обработок других элементов;
• 3) логарифмическая сложность 0(log 2 w), 0(nog 2 n). Иногда используются и другие основания логарифма;
• 4) полиномиальная сложность 0(я 2), 0(/г 3), 0(я 4),...;
• 5) экспоненциальная сложность 2 п, 3",....

При увеличении размера входа сложность каждого последующего типа функций растет быстрее, чем предыдущего (кроме 0(log 2 /?)). Для достаточно большого объема входных данных предпочтительнее использовать алгоритмы с меньшей сложностью.

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

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

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

После выбора значимых операций они делятся на две категории:

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

Непосредственный подсчет или оценка количества выполняемых операций позволяет оценить Т(п).

Для оценки порядка сложности можно использовать анализ программного кода, реализующего алгоритм. При этом:

• алгоритмы без циклов и рекурсивных вызовов имеют сложность порядка 0(1). Таким образом, операции присваивания, ввода и вывода данных, условные конструкции имеют константную сложность;
• если две части программного кода имеют сложности 0(J { (ri)) и 0(J 2 (n)), то последовательное выполнение имеет сложность

• если тело цикла выполняется один раз для каждого элемента входных данных, то сложность выполнения цикла имеет порядок 0(п)0( 1) = 0(п);
• порядок сложности выполнения вложенных циклов вычисляется по правилу произведения 0(J x (n)f 2 (n)) = 0(/,(/?))- 0(J 2 (ri)). Если каждый из них имеет сложность порядка 0(п), выполнение вложенных циклов имеет сложность порядка 0(п 2).

Пример 1.3

Определить порядок сложности алгоритма программы на языке

Pascal, приведенного в листинге 1.2. Строки программы пронумерованы в виде комментариев (см. параграф 2.6).

Листинг 1.2

{01} for i:=l to n do

{02} begin

{03} write("Введите элемент массива

с индексом ",i,": ");

{04} Readln(MyArray[i]);

{05} end;

{06} for i:=l to n do

{07} for j:=1 to n do

{08} begin

{09} write("Введите элемент массива

с индексами ", i, ",", j, " : ");

{10} Readln(МуDArray);

{11} end;

Решение

Строки 02, 05, 08, 11 не содержат исполняемых операторов, поэтому при определении порядка они не учитываются.

Строки 03 и 04 имеют порядок 0(1). Последовательное их выполнение имеет порядок 0(1) + 0(1) = 0(1). Аналогично, последовательное выполнение строк 09 и 10 имеет сложность 0(1).

Цикл в строках 01-05 имеет сложность порядка О(п), вложенные циклы в строках 06-11 - порядка 0(п 2). Итоговая сложность алгоритма имеет порядок

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

Привет! Сегодняшняя лекция будет немного отличаться от остальных. Отличаться она будет тем, что имеет лишь косвенное отношение к Java. Тем не менее, эта тема очень важна для каждого программиста. Мы поговорим об алгоритмах . Что такое алгоритм? Говоря простым языком, это некоторая последовательность действий, которые необходимо совершить для достижения нужного результата . Мы часто используем алгоритмы в повседневной жизни. Например, каждое утро перед тобой стоит задача: прийти на учебу или работу, и быть при этом:

• Одетым
• Чистым
• Сытым

1. Проснуться по будильнику.
2. Принять душ, умыться.
3. Приготовить завтрак, сварить кофе/заварить чай.
4. Поесть.
5. Если не погладил одежду с вечера - погладить.
6. Одеться.
7. Выйти из дома.

1. Купить или скачать в Интернете “Словарь русских личных имен” 1966 года издания.
2. Находить каждое имя из нашего списка в этом словаре.
3. Записывать на бумажку, на какой странице словаря находится имя.
4. Расставить имена по порядку, используя записи на бумажке.

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

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

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

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

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

Int index = 5; int item = list; 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 2 n ). Однако при замене базы логарифмы 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 . Например, задача о порядке перемножения матриц может быть решена за полилогарифмическое время на параллельной РАМ-машине .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обратно - существуют алгоритмы, которые работают за число шагов машины Тьюринга, ограниченных полиномиальной длиной бинарно закодированного входа, но не работают за число арифметических операций, ограниченное многочленом от количества чисел на входе. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Для двух целых чисел a {\displaystyle a} и b {\displaystyle b} время работы алгоритма ограничено O ((log ⁡ a + log ⁡ b) 2) {\displaystyle O((\log \ a+\log \ b)^{2})} шагам машины Тьюринга. Это число является многочленом от размера бинарного представления чисел a {\displaystyle a} и b {\displaystyle b} , что грубо можно представить как log ⁡ a + log ⁡ b {\displaystyle \log \ a+\log \ b} . В то же самое время число арифметических операций нельзя ограничить числом целых во входе (что в данном случае является константой - имеется только два числа во входе). Ввиду этого замечания алгоритм не работает в строго полиномиальное время. Реальное время работы алгоритма зависит от величин a {\displaystyle a} и b {\displaystyle b} , а не только от числа целых чисел во входе.

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы квазиполиномиального времени - это алгоритмы, работающие медленнее, чем за полиномиальное время, но не столь медленно, как алгоритмы экспоненциального времени. Время работы в худшем случае для квазиполиномиального алгоритма равно c . Хорошо известный классический алгоритм разложения целого числа на множители, , не является квазиполиномиальным, поскольку время работы нельзя представить как 2 O ((log ⁡ n) c) {\displaystyle 2^{O((\log n)^{c})}} для некоторого фиксированного c . Если константа "c" в определении алгоритма квазиполиномиального времени равна 1, мы получаем алгоритм полиномиального времени, а если она меньше 1, мы получаем алгоритм сублинейного времени.

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

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

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

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

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

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

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

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

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

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

Некоторые авторы определяют субэкспоненциальное время как время работы 2 o(n ) . Это определение допускает большее время работы, чем первое определение. Примером такого алгоритма субэкспоненциального времени служит хорошо известный классический алгоритм разложения целых чисел на множители, общий метод решета числового поля , который работает за время около 2 O ~ (n 1 / 3) {\displaystyle 2^{{\tilde {O}}(n^{1/3})}} , где длина входа равна n . Другим примером служит хорошо известный алгоритм для задачи изоморфизма графов , время работы которого равно 2 O ((n log ⁡ n)) {\displaystyle 2^{O({\sqrt {(}}n\log n))}} .

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

Точнее, SUBEPT является классом всех параметризованных задач (L , k) {\displaystyle (L,k)} , для которых существует вычислимая функция f: N → N {\displaystyle f:\mathbb {N} \to \mathbb {N} } с f ∈ o (k) {\displaystyle f\in o(k)} и алгоритм, который решает L за время 2 f (k) ⋅ poly (n) {\displaystyle 2^{f(k)}\cdot {\text{poly}}(n)} .

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

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

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

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

Временна́я сложность алгоритма это время \(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\)

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

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

Дополнительной памяти в эффективной реализации алгоритма практически не требуется, и она не зависит от входных данных, поэтому пространственная сложность \(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+86+172+688 = 989\)

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

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы так и не понимаете, что это значит, - эта статья для вас.

Оценка сложности

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

Допустим, некоторому алгоритму нужно выполнить 4n 3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n 3) , т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .

Примеры

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

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

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

Простейший пример - бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива - там его точно нет. Если же меньше, то наоборот - отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n 2) - квадратичная сложность

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

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

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

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