Определение сложности алгоритма
Получаемая в асимптотическом анализе оценка функции трудоемкости, называется сложностью алгоритма.
Следует иметь в виду, что существует несколько оценок сложности алгоритма.
Асимптотика функции трудоемкости - это операционная сложность. Кроме нее можно указать следующие виды сложностей.
Временная сложность - асимптотическая оценка времени работы алгоритма на входных данных длиною п. Очевидно, что при отсутствии распараллеливания вычислительных процедур время работы алгоритма однозначно определяется числом выполняемых операций. Постоянные коэффициенты, выражающие длительность выполнения операций, не влияют на порядок временной сложности, поэтому формулы операционной и временной сложностей часто совпадают друг с другом.
Емкостная сложность - асимптотическая оценка числа одновременно существующих скалярных величин при выполнении алгоритма на входных данных длиною п.
Структурная сложность - характеристика количества управляющих структур в алгоритме и специфики их взаиморасположения.
Когнитивная сложность - характеристика доступности алгоритма для понимания специалистами прикладных областей.
Виды и обозначения асимптотик
В асимптотическом анализе алгоритмов принято использовать обозначения математического асимптотического анализа. При этом рассматриваются три оценки (асимптотики) трудоемкости алгоритмов , которые обозначаются так:
- 1) /(я) = О^(п)) - асимптотически точная оценка функции трудоемкости /(«), или операционная сложность алгоритма;
- 2) /(п) = 0{§{п)) - асимптотически точная верхняя оценка функции трудоемкости /(п );
- 3) /(л) = ?2(#(л)) - асимптотически точная нижняя оценка функции трудоемкости /(п).
Вместо обозначения С1^(п)) очень часто используется более простое о(^(«)) с буквой «о» строчное курсивное.
Поясним семантику формул на примере: если записано /(я) = 0(^2(л)), ТО ЭТО означает, ЧТО функция g(n)=og 2 (n) является асимптотически точной оценкой функции трудоемкости /(«). По сути дела имеет место двухпозиционное определение в форме утверждения:
Если f(n) = @(log 2 («)),
mo g(n) = log 2 (л) - асимптотически точная оценка f(n).
Заметим, что постоянный множитель не влияет на порядок сложности алгоритма, поэтому основание логарифма опускают при указании логарифмической трудоемкости, и пишут просто /(л) = @(1о§(л)), подразумевая у логарифма произвольное основание большее единицы.
Формальные определения асимптотик
Асимптотически точная оценка функции трудоемкости с, с 2 , л 0 , такие что при л>л 0 функция /(л) с точностью до постоянных множителей не отличается от функции g(л), то функция g(n) называется асимптотически точной оценкой функции /(л).
- 3 с ] , с 2 е
Ж, с х
> 0, с 2 >
0:
- (3 л 0 е К, л 0 > 0: (/л е К, л > л 0:0 g(n) /(л) = 0(?(л)),
где 9^, N - множества всех вещественных и натуральных чисел соответственно.
Асимптотически точная верхняя оценка функции трудоемкости вербально определяется так: если существуют положительные числа с и л 0 , такие что при л>л 0 функция /(л) растет не быстрее, чем функция g(n) с точностью до постоянного множителя с, то функция g{n) называется асимптотически точной верхней оценкой функции Ап).
Более точная формальная запись определения имеет вид:
- 3 с
е % с >
0:
- (3 л 0 е X, л 0 > 0: (/л е К, л > л 0:0 с? #(л))) 0(g(n))
Асимптотически точная нижняя оценка функции трудоемкости вербально определяется так: если существуют положительные числа с и л 0 , такие что при л>л 0 функция /(л) растет не медленнее, чем функция g{n) с точностью до постоянного множителя с, то функция?(л) называется асимптотически точной нижней оценкой функции
Более точная формальная запись определения имеет вид:
- 3 с
е 9^, с
> 0:
- (3 я 0 е X, я 0 > 0: (/я е К, я > я 0: 0 с? g(n)
/(я) = 0.^(п))
Заметим, следующее:
- 1) неравенствам, указанным в формальных определениях асимптотик, в общем случае может удовлетворять не одна, а некоторое множество функций, часто с бесчисленным множеством членов, поэтому конструкции Q(g(n )), 0^{п)) и 0.^(п)) символизируют множества функций , с которыми сопоставляется исследуемая функция трудоемкости /(я); в силу этого в обозначениях асимптотик вида /(я) = 0(?(я)), /(/0 = О(? тах (л)), Дя) = ?2(? т1п (я)) вместо знака «=» рациональнее было бы использовать знак «е»;
- 2) конструкции (д^{п )), 0^{п)) и ?1^{п)), использованные в качестве обозначений некоторых величин, следует читать соответственно так: любая функция, совпадающая, растущая не быстрее и растущая не медленнее g{n).
Совпадение и различие асимптотик
Обратим внимание на следующий факт: оценка /(я) = 0(?(я)) устанавливает для /(я) одновременно и верхнюю, и нижнюю оценки, поскольку ее определение предполагает справедливость отношения с г g(n)
Достаточно очевидно следующее свойство асимптотик: если оценка ф(п) = ©^(п)) существует, то справедливы равенства /(п ) = 0(^(я)) и /(я) = ?2(#(я)), т.е. верхние и нижние оценки трудоемкости совпадают друг с другом; если же /(я) = 0(? тах (я)) и ф(п) = С1^ тт (п )), и g max (n)фg m 1п (я), то не существует функции g(n), такой что /(я) = 0(?(я)).
Совпадение верхней и нижней оценок трудоемкости возможно в следующих случаях:
- 1) функция трудоемкости при всех значениях длины входа является детерминированной (неслучайной) функцией, т.е. количество выполняемых операций не зависит от конкретики значений исходных данных; таковыми, например, являются функции зависимостей количества операций умножения и деления от числа неизвестных величин в алгоритме решения систем линейных алгебраических уравнений методом ИЗ-разложения;
- 2) функция трудоемкости является случайной функцией, т.е. количество выполняемых операций зависит от конкретики исходных данных и (или) порядка их поступления, и можно указать функции / т|п (я), / тах (я), описывающие минимальное и максимальное количество операций, выполняемых исполнителем алгоритма при конкретной длине входа я, однако обе эти функции имеют одинаковые доминанты, - например, являются полиномами одного и того же порядка.
Следует помнить о существовании следующих трех важных правил, связанных с оценками порядка операционной сложности:
- 1) постоянные множители не имеют значения для определения порядка сложности, т.е. 0(к? g(n )) = 0(g(«)) ;
- 2) порядок сложности произведения двух функций равен произведению их сложностей, поскольку справедливо равенство:
- 0(gl (я) §2 (я)) = 0 (?| (я)) 0 (#2(я)) ;
- 3) порядок сложности суммы функций равен порядку доминанты слагаемых, например: 0(я э +п 2 +п) = 0(я 5).
В приведенных правилах использован символ только одной асимптотики 0(»), но они справедливы для всех асимптотических оценок - и для 0( ) , и &.{ ).
Во множестве элементарных функций можно указать список функционального доминирования: если -переменная, a,b - числовые константы, то справедливы следующие утверждения: я" доминирует я!; я! доминирует а"; а" доминирует Zj", если а>Ь а п доминирует п ь, если а > 1 при любом b е 9? ; п а доминирует а/, если а>Ь я доминирует log д (я), если а > 1.
Оценивание средней трудоемкости
В практике реальных вычислений существенный интерес представляет оценка /(я) математического ожидания трудоемкости М, поскольку в подавляющем большинстве случаев /(я) является случайной функцией. Однако в процессе экспериментальных исследований алгоритмов со случайной /(я) возникает дополнительная проблема - выбора количества испытаний для надежной оценки М. Преодоление этой проблемы является центральной задачей в . Предлагаемое в решение основано на использовании бета-распределения для аппроксимации /(я). Это весьма конструктивная и универсальная методика. Однако в современных условиях, когда производительность ЭВМ достаточно высока, во многих случаях можно использовать более простой способ выбора объема испытаний, основанный на контроле текущей вариативности значений f(n) - значения оцениваются до тех пор, пока вариативность оценок не станет меньше заданной погрешности.
Оценивание операционной сложности алгоритма
Сложность алгоритма может быть определена исходя из анализа его управляющих структур. Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Поэтому определение сложности алгоритма сводится в основном к анализу циклов и рекурсивных вызовов.
Рассмотрим алгоритм удаления к -го элемента из массива размером п , состоящий из перемещения элементов массива от (к + 1) -го до п -го на одну позицию назад к началу массива и уменьшения числа элементов п на единицу. Сложность цикла обработки массива составляет О(п-к), так как тело цикла (операция перемещения) выполняется п-к раз, а сложность тела цикла равна 0(1), т.е. является константой.
В рассматриваемом примере сложность охарактеризована асимптотикой 0(»), поскольку количество выполняемых операций в этом алгоритме не зависит от конкретики значений данных. Функция трудоемкости является детерминированной, и все виды асимптотик совпадают друг с другом: f(n) = Q(n-k), f(n) = 0(n-k) и f(n) = Q(n- к ). Об этом факте и свидетельствует указание именно ©( ). Использовать 0(*) и/или?2(*) следует только в том случае, если эти асимптотики различаются.
Тип цикла (for, while, repeat) не влияет на сложность. Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. Вложенность повторений является основным фактором роста сложности. В качестве примера приведем сложности хорошо известных алгоритмов поиска и сортировки для массива размером п:
- число операций сравнения в последовательном поиске: 0(я);
- число операций сравнения в бинарном поиске: 0(log 2 п );
- число операций сравнения в методе простого обмена (пузырьковая сортировка): 0(я 2);
- число операций перестановки в пузырьковой сортировке: 0{п 2);
Заметим, что число операций сравнения в методе простого обмена имеют асимптотику 0(п 2), а число операций перестановки имеет две различных асимптотики 0(п 2) и?2(0), потому что количество сравнений не зависит от конкретики значений сортируемых данных, в то время как количество перестановок определяется именно этой конкретикой. Перестановки могут не осуществляться вовсе, - если массив данных правильно упорядочен изначально, либо количество перестановок может быть максимальным - порядка п 2 , - если сортируемый массив исходно упорядочен в противном направлении.
Название функции g(n) в асимптотиках /(л) = @(^(л)) и /(«) = 0(g(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\)
- Записать \(n\) в двоичной системе счисления
- Заменить в этой записи каждую из 1 парой букв КХ, а каждый 0 – буквой К
- Вычеркнуть крайнюю левую пару КХ
- Читая полученную строку слева направо, встречая букву К возвести результат в квадрат, а встречая букву 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 | 23 | нечетное |
| 86 | 11 | нечетное |
| 172 | 5 | нечетное |
| 344 | 2 | |
| 688 | 1 | нечетное |
Результат \(43+86+172+688 = 989\)
Получили 10 операций сдвига и 4 операции сложения. Для справки, \(\log_2(23) \approx 4.52\) .
Глава 2. Сложность алгоритмов.
2.1 Временная и вычислительная сложность алгоритмов.
Временная сложность алгоритма (T (N ) , где N – размер задачи) – это время выполнения алгоритма, измеренное в шагах (инструкциях алгоритма, которые нужно выполнять для достижения результата). Т. е. это – число элементарных операций, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return).
Различают три разновидности временной сложности, которые зависят от комбинации входных данных при решении задачи (равнозначность, разряженность, упорядоченность и др. свойства входных данных).
https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60">
Случай T (N )= C * N 2 применим для квадратной матрицы.
Элементарные операции в данном случае – совокупность «+» и «*».
Если исходная матрица – единичная, то получаем Best Case.
Если в матрице половина элементов – 0, половина – 1, то получаем Average Case.
Константа С , которая не может быть точно выражена, характеризует влияние внешних факторов на время выполнения алгоритмов (быстродействие ЭВМ, скорость компиляции). Поэтому использование единиц времени для оценки временной сложности алгоритмов не совсем корректно. В этом случае говорят, что временная сложность алгоритма умножения матрицы на вектор пропорциональна N 2 .
2.2 O и Ω – нотации.
Характер поведения временной сложности при увеличении N (N ® ¥ ) называется асимптотической сложностью алгоритма.
Для описания скорости роста асимптотической сложности используется О-нотация. Когда говорят, что временная сложность алгоритма имеет порядок N 2 :
T (N )= O (N 2 )= O (f (N )),
То подразумевается, что существуют положительные константы C , n0= const (C >0), такие, что для всех N ³ N 0 выполняется неравенство
T (N ) £ C * f (N )
Это – верхняя граница оценки сложности.
Пример 2 :
Пусть Т(0)=1, Т(1)=4, …, Т(N )=(N +1)2 , тогда временная сложность этого алгоритма имеет порядок роста T (N )= O (N 2 ).
Можно показать, что для всех N > n 0 при n 0 = 1, C = 4 выполняется неравенство (1).
(N +1)2 £ 4* N 2
Пример 3 :
Если временная сложность записывается в виде полинома
T (N )= C 1 N 2 + C 2 N + C 3 ,
то такой алгоритм имеет порядок сложности, кратный степени максимального элемента полинома, т. к. он растет наиболее быстро при N ® ¥ :
T (N )= O (N 2 ).
Например:
3 n 2 +5 n +1 £ 5 n 2
" n ³ 1
Пример 4 :
Если некоторый алгоритм имеет сложность, кратную 3 n , тогда можно показать, что порядок роста скорости не может быть кратен O (2 n ):
T (N )=3 n ¹ O (2 n ).
Пусть существуют константы C , n 0 , такие, что выполняются неравенство:
3 n £ C *2 n , n > n 0 .
Отсюда получаем:
С ³ (3/2)2, n > n 0 .
Но при n ® ¥ не существует такой константы С , которая удовлетворяла бы данному неравенству.
Кроме верхней границы сложности существует и нижняя граница скорости роста временной сложности:
T (N ) ³ W (f (N ))
Неравенство (2) подразумевает, что существует некоторая константа С , для которой при N ® ¥ временная сложность
T (N ) ³ C * f (N ).
Учитывая сложность точного определения T(N) (асимптотической временной сложности), в зависимости от размеров исходных данных на практике используют нижние и верхние границы временной сложности алгоритма:
T (N ) = q (f (N ))
В зависимости от значения константы С скорость роста сложности алгоритма может существенно меняться.
Пример 5 :
Пусть временная сложность записывается формулой
T(N)=3n2 –100n+6=O(n2)
3n2 >3n2 –100n+6, n ³ 1, C=3.
Если С1 » 0 (С1=0,00001) , тогда неравенство
10-5 n 2 > 3 n 2 –100 n +6, n ³ 1
не выполняется.
Но можно показать, что порядок роста сложности
3n2 –100n+6 ¹ O(N).
C*N < 3N2, N>C.
3n2 –100n+6=(n2)
C =2.29, n ³ n 0.
2.99* n 2 < 3 n 2 –100 n +6
Можно показать, что нижняя граница
3 n 2 –100 n +6 ¹ W (n 3 ) при С=1.
Неравенство 3 n 2 –100 n +6 ³ n 3 не выполняется.
3 n 2 –100 n +6= W (n )
C 1 = , n > n 0 .
https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src=">
f 1 (N )=100 n 2
f 2 (N )=5 n 3
n 0 =20 – критическая точка.
Другой причиной предпочтения алгоритмов с меньшим порядком сложности является то, что чем меньше порядок сложности, тем больший размер задачи N можно решить практически.
0 " style="margin-left:5.4pt;border-collapse:collapse;border:none">
n !
Пример 6:
Нужно учитывать, что больший порядок роста сложности алгоритмов как правило имеет меньшую константу С1 по сравнению с малым порядком роста сложности, характеризующимся константой С2 .
В этом случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для решения задач с малыми размерами данных (n ® 0 ).
Пусть заданы пять алгоритмов решения одной и той же задачи, имеющие сложности:
А1: 100 N
А2: 100 N * logN
А3: 10 N 2
А4: N 3
А5: 2 N
Тогда для задач с N =2 ¸ 9 более быстродействующим будет А5 (f (N ) ~ 4 ¸ 512 ). Другие алгоритмы при подстановке дадут существенно более низкие показатели.
При N =10 ¸ 58 предпочтительным оказывается А3.
При N =59 ¸ 1024 самым эффективным будет А2.
При N >1024 предпочтителен А1.
Для программ, состоящих из нескольких последовательно или параллельно выполняющихся алгоритмов, сложность оценивается по правилу сумм и правилу произведений .
Правило сумм : Пусть программа состоит из двух последовательно выполняющихся алгоритмов Р1 и Р2, для которых определены сложности O (f (n )) и O (g (n )) соответственно. Тогда временная сложность всей программы будет определяться как сумма временных сложностей каждого из алгоритмов:
T (n ) = T 1 (n )+ T 2 (n )
В общем случае получаем:
T(n) Þ O(max f(n), g(n))
Правило произведений: Пусть временная сложность программы, состоящей из двух параллельно выполняющихся алгоритмов, имеющих порядок сложности O (f (n )) и O (g (n )) соответственно, определяется как произведение временных сложностей каждого из алгоритмов:
T (n ) = T 1 (n )* T 2 (n )
В общем случае:
T (n ) Þ O (f (n )* g (n ))
Логарифмы.
2.3. Рекурсия.
Сложность рекурсивных алгоритмов оценить непросто в силу вложенности алгоритмических структур
f (n ) Þ f (n * f (n -1))
Например, для рекурсивного вычисления алгоритма n! Сложность будет зависеть от сложности каждого из алгоритмов, входящих в рекурсию.
В общем случае T (n ) ~ O (N ).
Другие рекурсивные алгоритмы в общем случае имеют временную сложность T (n ) ~ O (an ) , где a = const , что в результате дает суммарную сложность, большую, чем сложность не рекурсивного алгоритма решения этой же задачи.
2.4 Оценка сложности алгоритмов и программ.
2.4.2 Алгоритмы восстановления зависимостей.
В ряде случаев неизвестна структура программы, и можно лишь определить время ее работы при различных размерах входных данных T (N ) (сек.)
Для построения аналитической зависимости сложности программы оценивают функцию T (N ) на некотором интервале [ Nmin , Nmax ] . Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации.
Как правило, в качестве такой функции используют известные функции временной сложности: O (n !), O (XN ), O (NX ), O (logN ), O (https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">В результате эксперимента над программой была получена таблица временных сложностей:
В результате поиска аппроксимации функции была получена следующая аналитическая зависимость:
https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src=">
Пример 2:
Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.
В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.
Трудоемкость" href="/text/category/trudoemkostmz/" rel="bookmark">трудоемкостью (временем работы).
Полиномиальный или экспоненциальный характер работы алгоритма инвариантен относительно формы представления входных данных (двоичная, десятичная или другая система счисления).
Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени T (N )= O (Nm ) . Тогда все задачи, которые решаются таким алгоритмом, образуют Р-класс задач. Говорят, что эти задачи входят в Р.
Задачи, временная сложность которых экспоненциальна (T (N )= O (K N ) ), не входят в Р.
Замечание : Можно показать, что задачи с линейной сложностью входят в Р
T (N )= O (N 1 )
Введем класс NP-задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма.
Определим состояние алгоритма как совокупность адреса выполняемой в данный момент команды и значений всех переменных, что эквивалентно вектору состояния процесса. Поэтому большинство алгоритмов являются детерминированными, т. е. в них для любого состояния существует лишь одно допустимое следующее состояние (включая операции условия и выбора). Это значит, что такой алгоритм в каждый момент времени может делать что-то одно.
В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора.
НДА не является случайным или вероятностным алгоритмом. Он представляет собой алгоритм, который может находиться во многих состояниях (это эквивалентно параллельному решению задачи с множеством вариантов).
Пример :
 |
Детерминированный алгоритм (ДА) решал бы эту задачу последовательно (перебор всех вариантов, сравнение с критерием оптимальности K0 до тех пор, пока не выберет альтернативу А0).
НДА может одновременно (параллельно) получить все альтернативы и сравнить с K0, копируя самого себя в виде отдельного процесса для каждой альтернативы, которая выполняется независимо.
При этом если какая-либо копия обнаружит, что получен неправильный результат или результат не получен, то она прекращает свое исполнение. Если же копия находит решение, удовлетворяющее K0, то она объявляет об успехе, и все другие копии прекращают работу.
Т. о. НДА характеризуется тремя параметрами:
1. выбор – многозначная функция, значения которой являются элементами множества S;
2. неудача заставляет копию алгоритма прекратить работу;
3. успех заставляет все копии алгоритма прекратить работу и сформировать результат.
Очевидно, что никакое физическое устройство не способно на неограниченное недетерминированное поведение, значит, НДА является теоретическим методом.
Задачи, которые можно решить с помощью полиномиального НДА, образуют класс NP-задач.
2.5.2 NP -трудные и NP -полные задачи.
Задача, входящая в Р, является NP -трудной , если существует полиномиальный ДА (ПДА) ее решения, который модно использовать для получения решения всех задач, входящих в NP. Т. е. такая задача является NP-трудной, если она, по крайней мере, так же трудна, как любая задача, входящая в NP.
NP-трудная задача, принадлежащая NP, называется NP -полной задачей. Такие задачи не менее трудны, чем любая задача из NP. При этом существование ПДА для NP-трудной или NP-полной задачи означает, что классы Р и NP совпадают, т. е. возможно решение всех задач 3-го класса быстрым алгоритмом.
Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует ПДА, то его можно использовать для получения другого ПДА решения задач, входящих в NP.
Чтобы установить, что задача является NP-полной, необходимо доказать, что она принадлежит NP.
Идея использовать алгоритм решения одной задачи для получения алгоритма решения другой является одной из наиболее важных в теории алгоритмов.
Определение 1 : Задача Р1 преобразуется в задачу Р2, если любой частный случай задачи Р1 можно преобразовать за полиномиальное время в некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за полиномиальное время из решения частного случая задачи Р2.
https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56">
Например:
f 2 (xi )=(x 1 Ú x 2 ) Ù ( ) Ù ()
не является выполнимой, т. к. при любых xi f 2 (xi )= false .
Теорема :
Задача о выполнимости является NP-полной.
xi выбор (true, false)
if E(x1, x2, …, xN) then успех
else неудача
Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.
К-выполнимость .
К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.
Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*(х2) , содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.
E * (x 1 , x 2 ,…, xn ) ® E * (xi )
Для этого используется метод уменьшения порядка дизъюнкта
(a 1 Ú a 2 Ú … Ú a k )=(a 1 Ú a 2 Ú z ) Ù (a 3 Ú a 4 Ú … Ú a k Ú )
Применяя итерационный процесс разложения, можно получить Е* .
Найти алгоритм решения Е* проще, чем функции Е . Но при этом доказав выполнимость Е* , докажем выполнимость исходной функции Е .
Частный случай: при К=2 функция Е входит в Р.
Примерами задач NP-класса могут послужить также задачи на графах :
1) Определение максимума клик неориентированного графа (NP-трудная задача).
2) Задача определения полного подграфа (NP-полная задача).
3) Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).
4) Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).
5) Задача определения существования Гамильтонова цикла для графа (NP-полная задача).
6) Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).
7) Задача составления расписания (NP-полная задача).
2.6 Алгоритмически неразрешимые проблемы
Разделяют проблемы одиночные и массовые .
Например:
5+7=? – одиночная проблема.
х+у=? – массовая проблема.
Принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения задач, из которых вытекало бы существование парадоксальных объектов.
Например, парадоксами являются:
Пример 1:
10-ая проблема Гильберта.
Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит:
Найти алгоритм, определяющий некоторое целочисленное решение для произвольного диофантового уравнения
F (x , y , …)=0
Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных
anxn+an-1xn-1+…+a2x2+a1x+a0=0
Для приведенного уравнения существует частное решение, которое заключается в том, что всякий целочисленный корень xi является делителем a 0 . При этом a 0 раскладывают на простые множители и проверяют каждый множитель на соответствие корню.
В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде.
Пример 2:
Теорема Ферма:
Не существует таких целых чисел a , b , с, n (n >2) , для которых справедливо равенство
an + bn = cn
Эта теорема была доказана для многих значений n и проверена для частных случаев, однако до сих пор не создано общее доказательство теоремы.
Пример 3:
Проблема Гольдбаха.
Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему:
Доказать, что каждое целое число N ³ 6 может быть представлено в виде суммы трех простых чисел
N = a + b + c
Это значит, что нужно найти алгоритм, который позволил бы для любого целого числа N ³ 6 найти хотя бы одно разложение на три простых слагаемых.
Частый случай решения этой проблемы предложил Эйлер: для четных N эта проблема разрешима и равносильна разложению на два простых слагаемых.
И. Виноградов в 1937 г. доказал, что для нечетных N можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.
Постоянное время
Говорят, что алгоритм является алгоритмом постоянного времени (записывается как время 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 ).
Подквадратичное время
Некоторые примеры алгоритмов полиномиального времени:
Строго и слабо полиномиальное время
В некоторых контекстах, особенно в оптимизации , различают алгоритмы со строгим полиномиальным временем и слабо полиномиальным временем . Эти две концепции относятся только ко входным данным, состоящим из целых чисел.
Строго полиномиальное время определяется в арифметической модели вычислений. В этой модели базовые арифметические операции (сложение, вычитание, умножение, деление и сравнение) берутся за единицы выполнения, независимо от длины операндов. Алгоритм работает в строго полиномиальное время, если
- число операций в арифметической модели вычислений ограничено многочленом от числа целых во входном потоке, и
- память, используемая алгоритмом, ограничена многочленом от размеров входа.
Любой алгоритм с этими двумя свойствами можно привести к алгоритму полиномиального времени путём замены арифметических операций на соответствующие алгоритмы выполнения арифметических операций на машине Тьюринга . Если второе из вышеприведённых требований не выполняется, это больше не будет верно. Если задано целое число (которое занимает память, пропорциональную 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 следующим образом
QP = ⋃ c ∈ N DTIME (2 (log n) c) {\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})}Связь с NP-полными задачами
В теории сложности нерешённая проблема равенства классов P и NP спрашивает, не имеют ли все задачи из класса NP алгоритмы решения за полиномиальное время. Все хорошо известные алгоритмы для NP-полных задач, наподобие 3SAT, имеют экспоненциальное время. Более того, существует гипотеза, что для многих естественных NP-полных задач не существует алгоритмов с субэкспоненциальным временем выполнения. Здесь "субэкспоненциальное время " взято в смысле второго определения, приведённого ниже. (С другой стороны, многие задачи из теории графов, представленные естественным путём матрицами смежности, разрешимы за субэкспоненциальное время просто потому, что размер входа равен квадрату числа вершин.) Эта гипотеза (для задачи k-SAT) известна как гипотеза экспоненциального времени . Поскольку она предполагает, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени, некоторые результаты неаппроксимируемости в области аппроксимационных алгоритмов исходят из того, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени. Например, смотрите известные результаты по неаппроксимируемости задачи о покрытии множества .
Субэкспоненциальное время
Термин субэкспоненциальное время используется, чтобы выразить, что время выполнения некоторого алгоритма может расти быстрее любого полиномиального, но остаётся существенно меньше, чем экспоненциальное. В этом смысле задачи, имеющие алгоритмы субэкспоненциального времени, являются более податливыми, чем алгоритмы только с экспотенциальным временем. Точное определение "субэкспоненциальный" пока не является общепринятым , и мы приводим ниже два наиболее распространённых определения.
Первое определение
Говорят, что задача решается за субэкспоненциальное время, если она решается алгоритмом, логарифм времени работы которого растёт меньше, чем любой заданный многочлен. Более точно - задача имеет субэкспоненциальное время, если для любого ε > 0 существует алгоритм, который решает задачу за время O(2 n ε). Множество все таких задач составляет класс сложности SUBEXP , который в терминах DTIME можно выразить как .
SUBEXP = ⋂ ε > 0 DTIME (2 n ε) {\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)}Заметим, что здесь ε не является частью входных данных и для каждого ε может существовать свой собственный алгоритм решения задачи.
Второе определение
Некоторые авторы определяют субэкспоненциальное время как время работы 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 = DTIME (2 o (k) ⋅ poly (n)) . {\displaystyle {\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).}Точнее, 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)} .
Наверняка вы не раз сталкивались с обозначениями вроде 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) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.