Меры сложности алгоритмов. Классы задач P и NP.

Основы анализа алгоритмов.

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

      При анализе алгоритма определяется количество «времени», необходимое для его выполнения. Это не реальное число секунд или других промежутков времени, а приблизительное число операций, выполняемых алгоритмом. Число операций и измеряет относительное время выполнения алгоритма. Таким образом, иногда мы будем называть «временем» вычислительную сложность алгоритма. Фактически количество секунд, требуемое для выполнения алгоритма на компьютере непригодно для анализа, поскольку нас интересует только относительная эффективность алгоритма, решающего конкретную задачу. Действительно алгоритм не становится лучше, если его перенести на более быстрый компьютер, или хуже, если его исполнять на более медленном компьютере.

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

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

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

      Некоторые часто встречающиеся классы функций приведены в таблице. В этой таблице приведены значения функций из данного класса на широком диапазоне значений аргумента. Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Во-вторых, быстродействующие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего. Если, например, установлено, что алгоритму нужно x3-30x операций, то будем считать, что сложность алгоритма растёт как x3. Причина этого в том, что уже при 100 входных данных разница между x3 и x3 -30x составляет лишь 0,3%.

      Таблица классов роста функций

      Скорость роста сложности алгоритма играет важную роль, скорость роста определяется старшим, доминирующим членом формулы. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является. Алгоритмы можно сгруппировать по скорости роста их сложностей. Мы вводим три категории: алгоритмы, сложность которых растёт по крайней мере так же быстро, как данная функция (класс Ω(f) — читается Омега большое), алгоритмы, сложность которых растёт с той же скоростью(класс О(f) — читается О большое) и алгоритмы, сложность которых растёт медленнее, чем эта функция (класс θ(f) — читается Тета большое).

      Мы занимаемся эффективностью алгоритмов, поэтому класс Ω(f) не будет представлять для нас большого интереса: например в Ω(n2) входят все функции, растущие быстрее, чем n2.

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

      1. С формальной точки зрения функция g принадлежит классу O(f), если g(n)cf(n) для всех n, больших некоторого n0, и для некоторой положительной константы с.

      2. g принадлежит O(f), если lim(g(n)/f(n)) = c (n-> ) для некоторой константы с.

      По правилу Лопиталя можно заменить предел самих функций пределом их производных.

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

Алгоритмы полиномиальной сложности (класс Р).                    

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

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

Рассмотрим наиболее типичный вариант сортировки – пузырьковую сортировку. Алгоритм пузырьковой сортировки совершает несколько проходов по списку. При каждом проходе происходит сравнение соседних элементов. Если порядок соседних элементов неправильный, они меняются местами. Каждый проход начинается с начала списка. Сперва сравниваются 1 и 2 элементы, затем 2 и 3, потом 3 и 4 и т.д. Элементы с неправильным порядком в паре переставляются. При обнаружении на первом проходе наибольшего элемента списка он будет переставляться со всеми последующими пока не дойдет до конца списка. Поэтому при втором проходе нет необходимости производить сравнение с последним элементом. При втором проходе второй по величине элемент списка опустится во вторую позицию с конца и т.д. Стоит заметить, что при каждом проходе ближе к своему месту продвигается сразу несколько элементов, хотя гарантировано занимает окончательное положение лишь один.

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

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

Матрица – математический объект, эквивалентный двумерному массиву. Если число столбцов в первой матрице совпадает с числом строк во второй, то эти две матрицы можно перемножить:

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

Сводя три результата воедино, имеем следующую таблицу:

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

Алгоритмы недетерминированной полиномиальной сложности (класс NP задач).

Кроме практически разрешимых задач, относящихся к классу p – классу задач полиномиальной сложности, существует и другой класс задач: они практически неразрушимы и мы не знаем алгоритмов, способных решить их за разумное время. Эти задачи образуют класс NP – недетерминированной полиномиальной сложности.

Отметим только, что сложность всех известных детерминированных алгоритмов, решающих эти задачи, либо экспоненциально, либо факториальна. Сложность некоторых из них равна , где N – количество входных данных. В этом случае при добавлении к списку входных данных одного элемента время работы алгоритма удваивается. Если для решения такой задачи на входе из 10 элементов алгоритму требовалось 1024 операций, то на входе из 11 элементов число операций составит уже 2048. Это значительное возрастание времени при небольшом удлинении входа.

Термин «недетерминированные полиномиальные» характеризующие задачи из класса NP, объясняется следующим двухшаговым подходом к их решению. На первом шаге имеется недетерминированный алгоритм, генерирующий возможное решение такой задачи – что-то вроде попытки указать решение; иногда такая попытка оказывается успешной, и мы получаем оптимальный или близкий к оптимальному ответу, чаще нет (ответ далек от оптимального). На втором шаге проверяется, действительно ли ответ, полученный на 1 шаге, является решением исходной задачи. Каждый из этих шагов по отдельности требует полиномиального времени. Проблема, однако, в том, что мы не знаем, сколько раз нам придется повторить оба эти шага, чтобы получить искомое решение. Хотя оба шага и полиномиальны, число обращений к ним может быть экспоненциальным или факториальным.

К классу NP относится задача о коммивояжере. Нам задан набор городов и «стоимость» путешествия между любыми двумя из них. Нужно определить такой порядок, в котором следует посетить все города (по одному разу) и вернуться в исходный город, чтобы общая стоимость путешествия оказалась минимальной. Эту задачу можно применить, например, для определения порядка эффективного сбора мусора из баков на улицах города или выбора кратчайшего пути распространения информации по всем узлам компьютерной сети. Восемь городов можно упорядочить 40 320 возможными способами, а для десяти городов это число возрастает уже до 3 628 800. Поиск кратчайшего пути требует перебора всех этих возможностей. Предположим, что у нас есть алгоритм, способный подсчитать стоимость путешествия через 15 городов в указанном порядке. Если за секунду такой алгоритм способен пропустить через себя 100 вариантов, то ему потребуется больше четырех веков, чтобы исследовать все возможности и найти кратчайший путь. Даже если в нашем распоряжении имеется 400 компьютеров, все равно у них уйдет на это год, а ведь мы имеем дело лишь с 15 городами. Для 20 городов миллиард компьютеров должен будет работать параллельно в течение девяти месяцев, чтобы найти кратчайший путь. Ясно, что быстрее и дешевле путешествовать хоть как-нибудь, чем ждать, пока компьютеры выдадут оптимальное решение.

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

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

Наше краткое обсуждение того, насколько велико число возможных упорядочиваний вершин, должно было убедить Вас в том, что детерминированный алгоритм, сравнивающий все возможные способы упорядочивания. работает чересчур долго. Чтобы показать, что эта задача относится к классу NР, нам необходимо понять, как ее можно решить посредством описанной выше двухшаговой процедуры. В задаче о коммивояжере на первом шаге случайным образом генерируется некоторое упорядочивание городов. Поскольку это недетерминированный процесс, каждый раз будет получаться новый порядок. Очевидно, что процесс генерации можно реализовать за полиномиальное время: мы можем хранить список городов, генерировать случайный номер, выбирать из списка город с этим именем и удалять его из списка, чтобы он не появился второй раз. Такая процедура выполняется за 0(N) операций, где N — число городов. На втором шаге происходит подсчет стоимости путешествия по городам в указанном порядке. Для этого нам нужно просто просуммировать стоимости путешествия между последовательными парами городов в списке, что также требует 0(N) операций. Оба шага полиномиальны, поэтому задача о коммивояжере лежит в классе NP. Времяемкой делает ее именно необходимое число итераций этой процедуры.

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

       Сведение задачи к другой задаче

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

Поясним наше рассуждение примером. Пусть первая задача состоит и том, чтобы вернуть значение «да» в случае, если одна из данных булевских поименных имеет значение «истина», и вернуть «нет» в противоположном случае. Вторая задача заключается в том, чтобы найти максимальное значение в списке целых чисел. Каждая из них допускает простое ясное решение, но предположим на минуту, что мы знаем решение задачи о списке максимума, а задачу про булевские переменные решать не умеем. Мы хотим свести задачу о булевских переменных к задаче о максимуме целых чисел. Напишем алгоритм преобразования набора значений булевских переменных в список целых чисел, который значению «ложь» сопоставляет число 0, а значению «истина»— число 1. Затем воспользуемся алгоритмом поиска максимального элемента в списке. По тому, как составлялся список, заключаем, что этот максимальный элемент может быть либо нулем, либо единицей. Такой ответ можно преобразовать в ответ в задаче о булевских переменных, возвращая «да», если максимальное значение равно 1, и «нет», если оно равно 0.

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

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