(Применить процедуру MergeSort для сортировки первой половины списка List:
Применить процедуру MergeSort для сортировки второй половины списка List:
Применить процедуру MergeLists для объединения первой и второй половины списка List и получения отсортированной версии List )
Чтобы проанализировать сложность этого алгоритма, сначала найдем количество сравнений записей списка, необходимое для слияния списка длиной г со списком длиной s. Процесс слияния заключается в последовательном сравнении записей из одного списка с записями другого и помещении меньшего значения в выходной список. Таким образом, каждый раз, когда производится сравнение, количество оставшихся записей уменьшается на одну. Так как алгоритм начинает работать на г + s записей, мы делаем вывод, что процесс слияния двух списков потребует не более г + s сравнений.
Теперь рассмотрим алгоритм сортировки слиянием полностью. Он решает задачу сортировки списка длиной n так, что исходная задача сортировки разделяется на две меньших, когда сортируются списки длиной приблизительно "/4. Эти две задачи, в свою очередь, делятся еще раз, и мы получаем четыре задачи сортировки списков длиной приблизительно "Д. Этот процесс деления можно представить при помощи дерева на рис. 4, где каждый узел соответствует одной задаче в рекурсивном процессе, а ветви, исходящие из каждого узла, — это задачи меньшего размера, полученные из родительской задачи. Следовательно, мы можем найти общее количество сравнений, производимых в процессе сортировки, сложив количество сравнений, найденное в узлах дерева.
Сначала определим количество сравнений на каждом уровне дерева. Задача каждого узла на определенном уровне дерева — сортировать уникальный сегмент исходного списка. Это делается при помощи процесса слияния и, следовательно, требует сравнений не больше, чем есть записей в сегменте списка, что мы уже показали. Поэтому на каждом уровне дерева количество сравнений будет не больше общего количества записей в сегментах списка, а так как сегменты на данном уровне дерева являются непересекающимися частями исходного списка, конечное число сравнений будет не больше длины исходного списка. Следовательно, на каждом уровне дерева потребуется не более n сравнений. (Конечно, на нижнем уровне выполняется сортировка списков длиной 1 или менее, и сравнения не требуются вовсе.)
Теперь подсчитаем количество уровней в дереве. Для этого обратите внимание, что процесс деления задач на меньшие продолжается, пока не будут получены списки длиной менее двух. Поэтому количество уровней в дереве определяется количеством возможных операций деления на два, начиная со значения п до получения результатов, не превышающих единицу, то есть lg n. Точнее, в дереве может быть не более [lg n] уровней, требующих сравнений, где обозначение [lg n] — это округление lg n до ближайшего целого, большего lg n.
Наконец, общее количество сравнений, которые выполняет алгоритм сортировки слиянием при сортировке списка длиной n, получается умножением количества сравнений на каждом уровне на количество уровней, на которых требуются сравнения. Мы делаем вывод, что оно не превышает n [lg n]. Так как график функции nF[lg n]имеет ту же форму, что и график n lg n, то алгоритм сортировки слиянием принадлежит О(n lg n). Учитывая тот факт, что сложность задачи сортировки равна Θ(n lg n), можно утверждать, что алгоритм сортировки слиянием является оптимальным решением задачи сортировки.
Полиномиальные и не полиномиальные задачи.Предположим, что f(n) и g{ni) — математические выражения. Утверждение, что g(n) ограничена f(ni), означает, что, вычисляя эти выражения на растущих значениях и, значения f(n) в итоге становятся больше значений g(n) и превышают g(n) на всех дальнейших значениях п. Другими словами, то, что g(n) ограничена f(n), означает, что график f(n) находится выше графика g(n) для «больших» значений n. Например, выражение lg n ограничено n (рис. 6, а), а n lg n ограничено n2 (рис. 6, б).
Рисунок 6 – Графики математических выражений
Мы называем задачу полиномиальной (polynomial problem), если она принадлежит О(f(n)), где f{n) — это полином (многочлен), или это выражение ограничено полиномом. Набор всех полиномиальных задач обозначается Р. Обратите внимание, что наши предыдущие исследования показали, что задачи поиска в списке и сортировки списка принадлежат Р. Утверждение о том, что задача является полиномиальной, говорит о времени, необходимом для решения задачи. Мы часто говорим, что задача из Р может быть решена в полиномиальное время или что у этой задачи решение с полиномиальным временем.
Поиск задач, принадлежащих Р, является одной из главных проблем вычислительной техники, так как он тесно связан с вопросами о том, существует ли для задач практическое решение. Действительно, задачи, не входящие в Р, характеризуются очень большим временем выполнения, даже для небольших входов. Например, представим себе задачу, решение которой выполняется за 2n шагов. Экспоненциальное выражение 2n не ограничено ни одним полиномом. Действительно, если f{n) — полином, то с увеличением значения n мы обнаружим, что значения 2n всегда будут больше значений f(n). Это означает, что алгоритм сложности Θ(2n) в общем случае будет менее эффективным, и для его выполнения потребуется больше времени, чем для алгоритма сложности Θ(f(n)). Говорят, что для алгоритма, сложность которого определяется экспоненциальным выражением, требуется экспоненциальное время.
Рассмотрим пример. Представьте проблему перечисления всех возможных подгрупп, которые можно сформировать из группы, состоящей из n человек. Так как таких подгрупп может быть 2 n — 1 (мы считаем подгруппой всю группу, но не допускаем пустых подгрупп), любой алгоритм для решения этой задачи должен состоять минимум из 2 n - 1 шагов, и его сложность будет, по крайней мере, равна этому значению. Но выражение 2 n - 1, будучи экспоненциальным, не ограничено ни одним полиномом. Следовательно, любое решение этой задачи по мере увеличения размера группы, из которой выбираются подгруппы, требует огромного времени выполнения.
В противоположность задаче о подгруппах, сложность которой велика только из-за размера выхода, существуют задачи, чья сложность может быть высокой, даже если конечный выход — это просто ответ «да» или «нет». Например, способность отвечать на вопросы о правдивости утверждений, требующих сложения действительных чисел. Мы легко можем сказать, что ответом на вопрос «Правда ли, что существует действительное число, которое при сложении с самим собой дает значение 6?» будет «да», а на вопрос «Правда ли, что существует ненулевое действительное число, которое при сложении с самим собой дает 0?» — «нет». Однако если подобные вопросы становятся все более сложными, наша способность отвечать на них ослабевает. Если мы столкнемся с большим количеством подобных вопросов, то, вероятно, захотим воспользоваться компьютерной программой для ответа на них. К сожалению, поиск ответов на эти вопросы требует экспоненциального времени, поэтому в итоге компьютеры не могут сохранять регулярность при ответе на все более сложные вопросы.
То, что теоретически разрешаемые проблемы, не принадлежащие Р, имеют огромную временную сложность, заставляет нас признать, что их невозможно решить с практической точки зрения. Ученые, занимающиеся вычислительной техникой, называют такие задачи трудно разрешимыми. В свою очередь, задачи, для которых существуют практические решения, содержатся в Р. Поэтому понимание границ класса Р стало важной областью исследований вычислительной техники.
NP-задачи.Рассмотрим задачу коммивояжера, которая состоит в том, что коммивояжеру необходимо посетить всех его клиентов в различных городах, не превышая заданной длины пути, которую обеспечивает бюджет поездки. Его задача, следовательно, заключается в поиске пути (начиная от дома, через все необходимые города, и до возвращения домой), итоговая стоимость перемещения по которому не превышает проездных денег.
Традиционное решение этой задачи — последовательно рассматривать возможные пути, сравнивая длину каждого с пределом проездных денег, пока не будет найден подходящий путь или все возможности не будут исчерпаны. Однако этот подход требует неполиномиального времени решения. С увеличением количества городов количество путей, которые потребуется проверить, увеличивается быстрее любого полинома. Следовательно, решение задачи коммивояжера для большого количества городов таким способом невозможно.
Мы делаем вывод, что для решения задачи в разумное время требуется более быстрый алгоритм. Наш аппетит подогревается подозрением, что, если подходящий путь существует и мы выберем его первым, решение будет найдено очень быстро. В частности, следующий список команд можно быстро выполнить и получить возможное решение задачи:
Взять один из возможных путей и подсчитать общую длину пути.
if (длина пути не превышает допустимой)
then (объявить об успехе)
else (ничего не объявлять)
Но этот набор команд не является алгоритмом в техническом смысле. Его первая инструкция двусмысленна — она не указывает, какой из путей выбрать и из чего исходить при принятии решения. Она полагается на фантазию механизма выполнения программы, предоставляя выбор решения ему. Мы говорим, что такие инструкции недетерминированы, и называем «алгоритм», содержащий подобные указания, недетерминированным, алгоритмом (nondeterministic algorithm).
Обратите внимание, что с увеличением количества городов время, необходимо для выполнения этого недетерминированного алгоритма, увеличивается достаточно медленно. Процесс выбора пути заключается в простом выводе списка городов, на что требуется время, пропорциональное количеству городов. Кроме того, время, необходимое для вычисления полной длины выбранного пути, также пропорционально количеству городов, а время сравнения пути с предельно допустимым не зависит от числа городов. Следовательно, время выполнения недетерминированного алгоритма ограничено полиномом. Поэтому задачу о коммивояжере можно решить при помощи недетерминированного алгоритма в полиномиальное время.
Конечно, наше недетерминированное решение не идеально. Оно основано на случайном выборе. Однако его существования достаточно для предположения, что, возможно, есть и детерминированное решение задачи коммивояжера, которое выполняется в полиномиальное время. Правда это или нет — пока что открытый вопрос. В действительности, задача коммивояжера — лишь одна из задач, для которых известны недетерминированные решения, выполняемые в полиномиальное время, и для которых детерминированного решения с полиномиальным временем пока что не найдено. Дразнящая эффективность недетерминированных решений этих задач заставляет надеяться, что однажды будут найдены и эффективные детерминированные решения, но большинство убеждены, что эти проблемы все же слишком сложны и выходят за рамки возможностей эффективных детерминированных алгоритмов.
Во многих случаях лишь тонкая грань отделяет детерминированные алгоритмы от недетерминированных. Но различие между ними достаточно очевидно и существенно. Детерминированный алгоритм не надеется на творческие способности механизма, выполняющего алгоритм, тогда как для недетерминированного «алгоритма» они могут быть достаточно важны. Например, сравните команды
Дойдите до следующего перекрестка и поверните направо или налево.
и
Дойдите до следующего перекрестка и поверните направо или налево в зависимости от того, что скажет вам человек, стоящий на углу.
В обоих случаях действие, которое выполнит инструктируемый, не определено до начала выполнения команды. Однако первая команда требует от человека последовать направлению, выбранному им самостоятельно, то есть это недетерминированная инструкция. Вторая команда не предъявляет подобных требований к человеку — он получает инструкции на каждом шаге. Если первую команду выполнят несколько человек, то некоторые из них повернут направо, а другие — налево. Если несколько человек выполнят вторую команду и получат одинаковую информацию, то все повернут в одном направлении. В этом и заключается важное различие между детерминированными и недетерминированными «алгоритмами». Если детерминированный алгоритм выполнять несколько раз с одинаковыми входными данными, то выполненные действия всегда будут одинаковыми. В то же время недетерминированный алгоритм в одних и тех же условиях может привести к получению различных результатов.
Задача, которая может быть решена за полиномиальное время при помощи недетерминированного алгоритма, называется недетерминированной полиномиальной задачей (nondeterministic polynomial problem), или NP-задачей. Класс NP-задач обозначается NP. Обратите внимание, что все задачи из Р также принадлежат NP, так как к любому (детерминированному) алгоритму можно добавить недетерминированную комайду, не влияющую на работу алгоритма.
Ответа на вопрос, все ли NP-задачи находятся в Р, пока что нет, что демонстрирует нам задача коммивояжера. Возможно, это самая известная нерешенная задача вычислительной техники на сегодняшний день. Ее решение могло бы иметь значительные последствия. Например, в следующем разделе мы узнаем, что существуют системы шифрования, целостность которых зависит от огромного количества времени, необходимого для решения задач, схожих с задачей коммивояжера. Если окажется, что эффективные решения подобных задач существуют, такие системы шифрования будут подвергнуты риску.
Усилия по поиску ответа на вопрос, совпадает ли класс NP с классом Р, привели к обнаружению в классе NP нового класса задач, известного как NP-полные задачи (NP-complete problem). У этих проблем есть общее свойство, которое заключается в том, что решение с полиномиальным временем любой из них обеспечило бы решение с полиномиальным временем для всех остальных NP-задач. То есть, если найдется (детерминированный) алгоритм для решения одной из NP-полных задач в полиномиальное время, то этот алгоритм можно было бы расширить для решения всех остальных задач из NP в полиномиальное время. Следовательно, было бы доказано, что класс NP совпадает с классом Р. Задача коммивояжера является одной из NP-полных задач.
Подведем итог. Мы обнаружили, что задачи могут быть разрешимыми (имеющими алгоритмическое решение) и неразрешимыми (для которых нет алгоритмического решения), что показано на рис. 7. Более того, в классе разрешимых задач есть два подкласса. Первый — это набор полиномиальных задач, то есть задач, имеющих практическое решение. Второй представляет собой не полиномиальные задачи, практическое решение для которых может быть найдено только для относительно небольших и тщательно отобранных входов. И в заключение, существуют загадочные NP-задачи, не поддающиеся точной классификации.
Рисунок 7 – Графическое представление классификации задач
Контрольные вопросы
1. Как работает машина Тьюринга?
2. Что означает понятие «проблема останова»?
3. Что означает понятие «невычислимая функция»?
4. Какую проблему невозможно решить с помощью любой алгоритмической системы?
5. Какая классификационная система лежит в основе оценки сложности задач?
6. Что означает понятие «полиномиальные и не полиномиальные задачи»?
7. Что означает понятие «детерминированные и недетерминированные алгоритмы»?
