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

Для начала сосредоточимся на анализе времени выполнения в худшем случае: нас будет интересовать граница наибольшего возможного времени выполнения алгоритма для всех входных данных заданного размера N и закономерность ее масштабирования с изменением N.

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

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

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

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

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

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

Естественный алгоритм «грубой силы» для такой задачи будет перебирать все идеальные паросочетания и проверять каждое из них на устойчивость.

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

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

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

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

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

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

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