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

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

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

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

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

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

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

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

Например, как упоминалось в главе 2, естественный алгоритм «грубой силы» для поиска ближайшей пары среди n точек на плоскости просто проверяет все Θ(n2) расстояний с (полиномиальным) временем выполнения Θ(n2).

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

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