Глава 5 Разделяй и властвуй

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

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

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

У многих ситуаций, в которых применяется принцип «разделяй и властвуй» (включая перечисленные), есть нечто общее: естественный алгоритм «грубой силы» может выполняться за полиномиальное время, а стратегия «разделяй и вла- ствуй» способна сократить время выполнения до многочлена меньшей степени. В этом отношении он отличается от многих задач из предыдущих глав, например от задач, в которых алгоритм «грубой силы» работал с экспоненциальным време- нем, а целью разработки более сложного алгоритма был переход к полиномиально- му времени. Например, как упоминалось в главе 2, естественный алгоритм «грубой силы» для поиска ближайшей пары среди n точек на плоскости просто проверяет все Θ(η2) расстояний с (полиномиальным) временем выполнения Θ(η2). Принцип «разделяй и властвуй» позволит улучшить время выполнения до O(n log n). Таким образом, на высоком уровне общая тема этой главы не отличается от того, что мы уже видели ранее: улучшение результатов поиска «грубой силой» становится фун- даментальной концептуальной проблемой на пути эффективного решения задачи, и проектирование сложного алгоритма помогает с ней справиться. Просто разли- чия между поиском методом «грубой силы» и улучшенным решением не всегда означают различия между экспоненциальным и полиномиальным временем.

5.1.

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

Еще по теме Глава 5 Разделяй и властвуй:

  1. Глава 23 Разделяйте его интересы
  2. Разделяющее мышление
  3. Разделяющее двойственное мышление
  4. Разделяющее мышление.
  5. Характеристики современного разделяющего ума-эго
  6. Происхождение современного разделяющего ума-эго
  7. Характеристики разделяющего и отрицающего ума-эго
  8. Технологии, разделяемые по типам технологической неопределенности.
  9. Глава 8. Глава государства в зарубежных странах
  10. Глава рода
  11. Глава рода
  12. Глава 1