Оценка вычислительной сложности. Временная сложность алгоритма

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

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

Следует иметь в виду, что существует несколько оценок сложности алгоритма.

Асимптотика функции трудоемкости - это операционная сложность. Кроме нее можно указать следующие виды сложностей.

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

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

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

Когнитивная сложность - характеристика доступности алгоритма для понимания специалистами прикладных областей.

Виды и обозначения асимптотик

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

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)) функции трудоемкости /(«) используется для характеристики алгоритма. Таким образом, говорят об алгоритмах полиномиальной, экспоненциальной, логарифмической и т. д. сложности.

Наверняка вы не раз сталкивались с обозначениями вроде 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) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

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

Срок: 8 января 2010

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

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

Теория сложности вычислений - раздел теории вычислений, изучающий объем работы, требуемой для решения вычислительной проблемы.

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

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

Вычислительные проблемы

Экземпляры задач

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

Представление задачи

При рассмотрении вычислительных задач описанием экземпляра задачи является строка над алфавитом. Как правило, алфавит берется бинарным(т. е. множество {0,1}). Различные математические объекты должны быть соответствующим образом закодированы. Так, например, целые числа могут быть представлены в двоичной системе счисления, и графы могут быть закодированы непосредственно через их матрицы смежности или через их кодирование списков смежности в двоичной системе.

Задачи распознавания

Задачи распознавания является одним из центральных объектов исследования в теории сложности вычислений. Задача распознавания является особым типом вычислительных проблемы, ответом на которую является либо "да" или "нет"(1 или 0). Задачу распознавания можно сформулировать в виде задачи принадлежности входной строки к некоторому подмножеству (языку) множества всех входных строк. Входная строка проблемы принадлежит соответствующему языку тогда и только тогда, когда ответом на эту строку является «да». Таким образом задача распознавания - это задача распознавания принадлежности входной строку к некоторому языку.

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

Задачи поиска

Задачей поиска является вычислительная задача, где выходное значение является более сложным, чем в задаче распознавания (то есть, это не просто «да» или «нет»).

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

Существует парная зависимость между задачами распознавания и задачами поиска. Задачу поиска можно сформулировать в качестве задачи распознавания. Например, для задачи поиска «умножение двух чисел», соответствующая парная задача распознавания может быть представлена как множество троек (A, B, C) таких, что отношения A × B = C выполнено.

Измерение сложности

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

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

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

Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).

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

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

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

Сложность определяется исходя из вычислительной модели, в которой проводят вычисления.

Вычислительные модели

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

Машина Тьюринга

Маши́на Тью́ринга (МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

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

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

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

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

Машина Тьюринга является одной из основных моделей вычисления в теории сложности.

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

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

Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n - длина слова x.

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

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

Классы принято обозначать прописными буквами. Дополнение к классу C (то есть класс языков, дополнения которых принадлежат C) обозначается co-C.

Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса.

Класс P

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

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

Если для функции f существует машина Тьюринга M такая, что для некоторого числа c и достаточно больших n , то говорят, что она принадлежит классу FP, или полиномиальна по времени.

Класс P является одним из фундаментальных в теории сложности вычислений.

Класс NP

Классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания, время решения которых существенно зависит от размера входных данных; в то же время, существует алгоритм, который, получив наряду с описанием входных значений, некоторые дополнительные сведения (свидетеля решения), может достаточно быстро (за время, не превосходящее полинома от размера данных) решить задачу.

Более формально, язык L называется принадлежащим классу NP, если существуют двуместный предикат R(x, y) из класса P (т.е. вычислимый за полиномиальное время) и многочлен p такие, что для всякого слова x длины n условие «x принадлежит L» равносильно условию «найдётся y длины меньше p(n) такой, что верно R(x, y)». Слово y называется свидетелем принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L. Всякую задачу, принадлежащую NP, можно решить за экспоненциальное время перебором всех возможных свидетелей длины меньше p(n).

Пример задачи из NP: задача распознавания «Существование целочисленного решения системы линейных неравенств». Свидетель - решение системы неравенств. За полиномиальное время легко проверить, что решение-свидетель подходит.

Класс NP включает в себя класс P.

Открытые проблемы

В теории сложности вычислений существует множество нерешенных проблем, в основном они касаются вопросов разделения или вложенности тех или иных классов сложности. Одним из таких вопросов является проблема равенства классов P и NP.

Проблема равенства классов P и NP

В конечном счете проблема равенства классов P и NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время)?

Из определения классов P и NP сразу вытекает следствие: . Однако до сих пор ничего не известно о строгости этого включения, т.е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные NP-задачи (так называемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо.

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

Литература

Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи. Издательство Мир в 1982 году. - 420 с. Монография американских ученых посвящена решению сложных (в том числе и NP-трудных) комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории автоматов с примерами.
Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. - М.: «Вильямс», 2005. -

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

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

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

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

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

Задача 5.4 линейную сложность .

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

Текст программы

public class FibIv1 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> < 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m > 0) { k = j; j += i; i = k; } Xterm.println(" = " + j); } } }

Следующий вопрос вполне естественен - а можно ли находить числа Фибоначчи еще быстрее?

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

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

Текст программы

public class FibIv2 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); } }

На самом деле эта программа использует вызов функции возведения в степень { Math.pow(f,n) }, которая не может быть реализована быстрее, чем за логарифмическое время (). Про алгоритмы, в которых количество операций примерно пропорционально (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ().

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

Задача 5.5 . Напишите программу, печатающую -ое число Фибоначчи , которая имела бы логарифмическую сложность .

Текст программы

public class FibIv3 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> "); Xterm.print("f(" + n + ")"); if (n < 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) { if ((n&1) == 0) { n >>>= 1; c.square(); } else { n -= 1; b.mul(c); } } Xterm.println(" = " + b.fib()); } } } class Matrix { private long a, b, c, d; public Matrix(long a, long b, long c, long d) { this.a = a; this.b = b; this.c = c; this.d = d; } public void mul(Matrix m) { long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+d*m.c; long d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; } public void square() { mul(this); } public long fib() { return b; } }

Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long .

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

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

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

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

Для сравнения алгоритмов принято использовать обобщенную характеристику, называемую эффективностью. Говорят, что алгоритм Л, эффективнее алгоритма А 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). Итоговая сложность алгоритма имеет порядок

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