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

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

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

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

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

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

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Метод Обретения Внутренней Силы
  2. Метод Обретения Внутренней Силы
  3. Метод Ключ — способ наиболее короткого поиска этого особого состояния для производства саморегуляции.
  4. Поиск смысла жизни – это поиск бессмертия!
  5. Время сейчас такое – время мудрости пришло!
  6. 14. 4. Рабочее время и время отдыха
  7. Зарубка на носу Дай время себе, дай время ребенку
  8. ПОНЯТИЕ О МЕТОДАХ ОБУЧЕНИЯ. МЕТОД И ПРИЕМ. ОСНОВНЫЕ ПОДХОДЫ К КЛАССИФИКАЦИИ МЕТОДОВ ОБУЧЕНИЯ
  9. Обретение Внутренней Силы
  10. Обретение Внутренней Силы
  11. Ключ мог родиться только в России. Ключ к себе — ключ к системам. (это не метод среди методов, а Ключ к собственному методу)
  12. Места силы
  13. Зона силы
  14. ТОЧКА СИЛЫ
  15. Часть V. Россия — Обретение Силы