Вычислительная разрешимость - Основы анализа алгоритмов

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

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

2.1. Вычислительная разрешимость

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

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

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

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

Первые попытки определения эффективности

Первый серьезный вопрос, на который нужно ответить, выглядит так: как преобразовать размытое понятие “эффективный алгоритма” в нечто более конкретное?

На первый взгляд рабочее определение эффективности могло бы выглядеть так.

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

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

Однако в этом определении отсутствуют некоторые ключевые подробности, хотя нашей главной целью и является быстрое решение реальных задач на реальных компьютерах. Во-первых, в нем не указано, где и насколько хорошо реализуется алгоритм. Даже плохой алгоритм может быстро отработать с малым размером тестовых данных на исключительно быстром процессоре; даже хорошие алгоритмы могут быстро выполняться при небрежном программировании. Кроме того, какие входные данные можно считать “реальными”? Полный диапазон входных данных, которые могут встречаться на практике, неизвестен, а некоторые наборы данных могут создавать значительно больше сложностей при обработке. Наконец, предлагаемое определение не учитывает, насколько хорошо (или плохо) алгоритм масштабируется с ростом задачи до непредвиденных уровней. Типичная ситуация: два совершенно разных алгоритма примерно одинаково работают на входных данных размера 100; при 10-кратном увеличении размера данных один алгоритм продолжает работать быстро, а выполнение другого резко замедляется.

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

В качестве ориентира возьмем задачу устойчивых паросочетаний. У входных данных имеется естественный параметр — “размер” N; за него можно принять общий размер представления всех списков предпочтений, поскольку именно они будут передаваться на вход любого алгоритма для решения задачи. Значение N тесно связано с другим естественным параметром этой задачи: n, количеством мужчин и количеством женщин. Всего существуют 2n списков предпочтений, каждый из которых имеет длину n, поэтому мы можем считать, что N = 2n², игнорируя второстепенные подробности реализации представления данных. При рассмотрении задачи мы будем стремиться к описанию алгоритмов на высоком уровне, а затем проводить математический анализ времени выполнения как функции размера входных данных N.

Худшее время выполнения и поиск методом “грубой силы”

Для начала сосредоточимся на анализе времени выполнения в худшем случае: нас будет интересовать граница наибольшего возможного времени выполнения алгоритма для всех входных данных заданного размера N и закономерность ее масштабирования с изменением N. На первый взгляд повышенное внимание, уделяемое быстродействию в худшем случае, кажется излишне пессимистичным: а если алгоритм хорошо работает в большинстве случаев и есть лишь несколько патологических вариантов входных данных, с которыми он работает очень медленно? Конечно, такие ситуации возможны, но, как показали исследования, в общем случае анализ худшей производительности алгоритма неплохо отражает его практическую эффективность. Более того, при выборе пути математического анализа трудно найти практическую альтернативу для анализа худшего случая. Анализ среднего случая — очевидная альтернатива, при которой рассматривается производительность алгоритма, усредненная по набору “случайных” входных данных, — выглядит, конечно, заманчиво и иногда предоставляет полезную информацию, но чаще только создает проблемы. Как упоминалось ранее, очень трудно описать весь диапазон входных данных, которые могут встретиться на практике, поэтому попытки изучения производительности алгоритма для “случайных” входных данных быстро вырождаются в споры о том, как должны генерироваться случайные данные: один и тот же алгоритм может очень хорошо работать для одной категории случайных входных данных и очень плохо — для другой. В конец концов, реальные входные данные для этого алгоритма обычно берутся не из случайного распределения, поэтому риски анализа среднего случая больше скажут о средствах получения случайных данных, нежели о самом алгоритме.

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

Вернемся к примеру задачи устойчивых паросочетаний. Даже при относительно небольшом размере входных данных определяемое ими пространство поиска огромно (существует n! возможных идеальных паросочетаний между n мужчинами и n женщинами), а нам нужно найти паросочетание, которое является устойчивым. Естественный алгоритм “грубой силы” для такой задачи будет перебирать все идеальные паросочетания и проверять каждое из них на устойчивость. Удивительный в каком-то смысле вывод для нашего решения задачи устойчивых паросочетаний заключается в том, что для нахождения устойчивого паросочетания в этом колоссальном пространстве возможностей достаточно времени, пропорционального всего лишь N. Это решение было получено на аналитическом уровне. Мы не реализовали алгоритм и не опробовали его на тестовых списках предпочтений, а действовали исключительно математическими методами. Тем не менее в то же время анализ показал, как реализовать этот алгоритм на практике, и предоставил достаточно исчерпывающие доказательства того, что он существенно превосходит метод простого перебора.

Эта общая особенность встречается в большинстве задач, которыми мы будем заниматься: компактное представление, неявно определяющих колоссальное пространство поиска. Для большинства таких задач существует очевидное решение методом “грубой силы”: перебор всех возможностей и проверка каждого из них на соответствие критерию. Мало того, что этот метод почти всегда работает слишком медленно, чтобы его можно было признать практичным, — по сути, это обычная интеллектуальная увертка; он не дает абсолютно никакой информации о структуре изучаемой задачи. И если в алгоритмах, рассматриваемых в книге, и существует нечто общее, то это следующее альтернативное определение эффективности:

Предлагаемое определение эффективности (2): алгоритм считается эффективным, если он обеспечивает (на аналитическом уровне) качественно лучшую производительность в худшем случае, чем поиск методом “грубой силы”.

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

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

Полиномиальное время как показатель эффективности

Когда аналитики только начали заниматься анализом дискретных алгоритмов (а эта область исследований стала набирать темп в 1960-е годы), у них начал формироваться консенсус относительно того, какой количественной оценкой можно описать концепцию “разумного” времени выполнения. Время поиска в естественных комбинаторных задачах склонно к экспоненциальному росту относительно размера N входных данных; если размер увеличивается на единицу, то количество возможностей возрастает мультипликативно. Для таких задач хороший алгоритм должен обладать более эффективной закономерностью масштабирования; при возрастании размера входных данных с постоянным множителем (скажем, вдвое) время выполнения алгоритма должно увеличиваться с постоянным множителем C.

На математическом уровне эта закономерность масштабироваться может быть сформулирована так. Предположим, алгоритм обладает следующим свойством: существуют такие абсолютные константы c > 0 и d > 0, что для любого набора входных данных N время выполнения ограничивается cN^d примитивными вычислительными шагами. (Иначе говоря, время выполнения не более чем пропорционально N^d.) Пока мы намеренно будем сохранять неопределенность по поводу того, что считать “примитивным вычислительным шагом”, — но это понятие легко формализуется в модели, в которой каждый шаг соответствует одной ассемблерной команде на стандартном процессоре или одной строке стандартного языка программирования (такого, как C или Java). В любом случае при выполнении этой границы времени выполнения для некоторых c и d можно сказать, что алгоритм обеспечивает полиномиальное время выполнения или что он относится к категории алгоритмов с полиномиальным временем. Обратите внимание: любая граница с полиномиальным временем обладает искомым свойством масштабирования. Если размер входных данных возрастает с N до 2N, то граница времени выполнения возрастает с cN^d до c(2N)^d = c ∙ 2^dN^d, что соответствует замедлению с коэффициентом 2^d. Так как d является константой, коэффициент 2^d тоже является константой; как нетрудно догадаться, полиномы с меньшими степенями масштабируются лучше, чем полиномы с высокими степенями.

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

Предлагаемое определение эффективности (3): алгоритм считается эффективным, если он имеет полиномиальное время выполнения.

Если предыдущее определение казалось слишком расплывчатым, это может показаться слишком жестко регламентированным. Ведь алгоритм с временем выполнения, пропорциональным n¹⁰⁰ (а следовательно, полиномиальным), будет безнадежно неэффективным, не так ли? И неполиномиальное время выполнения n^{1+0,02(log n)} покажется нам относительно приемлемым? Конечно, в обоих случаях ответ будет положительным. В самом деле, как бы мы ни старались абстрактно оправдать определение эффективности в контексте полиномиального времени, главное оправдание будет таким: это определение действительно работает. У задач, для которых существуют алгоритмы с полиномиальным временем, эти алгоритмы почти всегда работают с временем, пропорциональным полиномам с умеренной скоростью роста, такой как n, n log n, n² или n³. И наоборот, задачи, для которых алгоритм с полиномиальной скоростью неизвестен, обычно оказываются очень сложными на практике. Конечно, у этого принципа есть исключения с обеих сторон: например, известны случаи, в которых алгоритм с экспоненциальным поведением в худшем случае обычно хорошо работает на данных, встречающихся на практике; а есть случаи, в которых лучший алгоритм с полиномиальным временем полностью непрактичен из-за больших констант или высокого показателя степени в полиномиальной границе. Все это лишь доказывает тот факт, что наше внимание к полиномиальным границам худшего случая — всего лишь абстрактное представление практических ситуаций. Но, как оказалось, в подавляющем большинстве случаев конкретное математическое определение полиномиального времени на удивление хорошо соответствует нашим наблюдениям по поводу эффективности алгоритмов и разрешимости задач в реальной жизни.

Еще одна причина, по которой математические формальные методы и эмпирические данные хорошо сочетаются в случае полиномиальной разрешимости, связана с огромными расхождениями между скоростью роста полиномиальных и экспоненциальных функций. Допустим, имеется процессор, выполняющий миллион высокоуровневых команд в секунду, и алгоритмы с границами времени выполнения n, n log₂ n, n², n³, 1,5ⁿ, 2ⁿ и n!. В табл. 2.1 приведено время выполнения этих алгоритмов (в секундах, минутах, днях или годах) для входных данных с размером n = 10, 30, 50, 100, 1000, 10 000, 100 000 и 1 000 000.

Таблица 2.1. Время выполнения (с округлением вверх) разных алгоритмов для входных данных разного размера (для процессора, выполняющего миллион высоко уровневых команд в секунду). Если время выполнения алгоритма превышает 10²⁵ лет, мы просто используем пометку “очень долго”

	n	n log2 n	n2	n3	1,5n	2n	n!
n = 10	< 1 с	< 1 с	< 1 с	< 1 с	< 1 с	< 1 с	4 с
n = 30	< 1 с	< 1 с	< 1 с	< 1 с	< 1 с	18 мин	1025 лет
n = 50	< 1 с	< 1 с	< 1 с	< 1 с	11 минут	36 лет	очень долго
n = 100	< 1 с	< 1 с	< 1 с	1 с	12 892 лет	1017 лет	очень долго
n = 1000	< 1 с	< 1 с	1 с	18 минут	очень долго	очень долго	очень долго
n = 10 000	< 1 с	< 1 с	2 минуты	12 дней	очень долго	очень долго	очень долго
n = 100000	< 1 с	2 с	3 часа	32 года	очень долго	очень долго	очень долго
n = 1 000 000	1 с	20 с	12 дней	31 710 лет	очень долго	очень долго	очень долго

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

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