2.6. РАЗДЕЛЯЙ И ВЛАСТВУЙ

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

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

элементов:

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

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

Алгоритм 2.3. Нахождение наибольшего и наименьшего элементов множества

Вход. Множество из элементов, где степень числа 2,2.

Выход. Наибольший и наименьший элементы множества

Метод. К множеству применяется рекурсивная процедура MAXMIN. Она имеет один аргумент представляющий собой множество такое, что при некотором и вырабатывает пару где а — наибольший и наименьший элементы в Процедура MAXMIN приведена на рис. 2.12.

Заметим, что сравнения элементов множества происходят только на шаге 3, где сравниваются два элемента множества из которых оно состоит, и на шаге 7, где сравниваются с Пусть число сравнений элементов множества которые надо произвести в процедуре MAXMIN, чтобы найти наибольший и наименьший элементы -элементного множества. Ясно, что Если то общее число сравнений, произведенных в двух вызовах процедуры MAXMIN (строки 5 и 6), работающей на множествах размера и еще два сравнения в

Рис. 2.12. Процедура для нахождения и MIN.

строке 7. Таким образом,

Решением рекуррентных уравнений (2.2) служит функция Легко проверить, что эта функция удовлетворяет (2.2) при и если она удовлетворяет (2.2) при где 2, то

т. е. она удовлетворяет (2.2) при Таким образом, индукцией по доказано, что удовлетворяет (2.2), если есть степень числа 2.

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

В предыдущем примере прием "разделяй и властвуй" позволил уменьшить количество сравнений лишь в фиксированное число раз. В следующем примере мы с помощью этого приема уменьшим даже порядок роста сложности алгоритма.

Рассмотрим умножение двух -разрядных двоичных чисел. Традиционный метод требует битовых операций. В методе,

Рис. 2.13. Разбиение цепочек, представленных в виде двоичных чисел.

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

Пусть х и у — два -разрядных двоичных числа. Снова будем считать для простоты, что есть степень числа 2. Разобьем х и у на две равные части, как показано на рис. 2.13. Если рассматривать каждую из этих частей как -разрядное число, то можно представить произведение чисел х и у в виде

Равенство (2.3) дает способ вычисления произведения х и у с помощью четырех умножений -разрядных чисел и нескольких сложений и сдвигов (умножений на степень числа 2). Произведение чисел х и у также можно вычислить по следующей программе:

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

где постоянная, отражающая сложение и сдвиги в выражениях, входящих в (2.4). Решение рекуррентных уравнений (2.5) ограничено сверху функцией

На самом деле можно показать, что в (2.5)

Доказательство проведем индукцией по где степень числа 2. Базис, т. е. случай тривиален. Если функция удовлетворяет (2.5) при то

так что она удовлетворяет (2.5) и при Отсюда следует, что Заметим, что попытка использовать в индукции вместо не проходит.

Для завершения описания алгоритма умножения мы должны учесть, что числа вообще говоря, имеют разрядов, и поэтому произведение нельзя вычислить непосредственным рекурсивным применением нашего алгоритма к задаче размера Вместо этого надо записать в виде где или 1. Аналогично запишем в виде Тогда произведение можно представить в виде

Слагаемое Ьгйг вычисляется с помощью рекурсивного применения нашего алгоритма умножения к задаче размера Остальные умножения в (2.6) можно сделать за время поскольку они содержат в качестве одного из аргументов либо единственный бит или либо степень числа 2.

Пример 2.6. Этот асимптотически быстрый алгоритм умножения целых чисел можно применять не только к двоичным, но и к десятичным числам. Проиллюстрируем это на примере:

Заметим, что алгоритм, основанный на (2.4), заменял одно умножение тремя сложениями и вычитанием (ср. с (2.3)). Почему такая замена приводит к асимптотической эффективности, можно

интуитивно объяснить тем, что умножение выполнить труднее, чем сложение, и для достаточно больших любое фиксированное число -разрядных сложений требует меньше времени, чем -разрядное умножение, независимо от того, какой из (известных) алгоритмов применяется. Вначале кажется, что уменьшение числа -разрядных произведений с четырех до трех может уменьшить общее время в лучшем случае на 25%. Однако соотношения (2.4) применяются рекурсивно для вычисления -разрядных, -разрядных и т. д. произведений. Эти -процентные уменьшения объединяются и дают в результате асимптотическое улучшение временной сложности.

Временная сложность процедуры определяется числом и размером подзадач и в меньшей степени работой, необходимой для разбиения данной задачи на подзадачи. Так как рекуррентные уравнения вида (2.2) и (2.5) часто возникают при анализе рекурсивных алгоритмов типа "разделяй и властвуй", рассмотрим решение таких уравнений в общем виде.

Теорема 2.1. Пусть и с — неотрицательные постоянные. Решение рекуррентных уравнений

где степень числа с, имеет вид,

Доказательство. Если степень числа в, то

Если то сходится и, следовательно,

Если то каждым членом этого ряда будет 1, а всего в нем членов. Поэтому Наконец, если то

что составляет или

Из теоремы 2.1 вытекает, что разбиение задачи размера (за линейное время) на две подзадачи размера дает алгоритм сложности Если бы подзадач было 3, 4 или 8, то получился бы алгоритм сложности порядка или соответственно.

С другой стороны, разбиение задачи на 4 подзадачи размера дает алгоритм сложности а на 9 и 16 — порядка и соответственно. Поэтому асимптотически более быстрый алгоритм умножения целых чисел можно было бы получить, если бы удалось так разбить исходные целые числа на 4 части, чтобы суметь выразить исходное умножение через 8 или менее меньших умножений. Другой тип рекуррентных соотношений возникает в случае, когда работа по разбиению задачи не пропорциональна ее размеру. Некоторые типы рекуррентных соотношений вынесены в упражнения.

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