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

Метод “разделяй и властвуй”

 

            Для решения той или иной задачи ее часто разбивают на части, находят их решение и затем из них получают решение всей задачи.

            В общем случае задача размерности n раскладывается на k задач с размерностями m1, m2,...,  mk таких, что m1+m2+...+mk<=n. Из этого исходят, в частности, почти все методы сортировки.

            В качестве примера рассмотрим умножение двух n-разрядных двоичных чисел. Традиционный метод требует O(n2) битовых операций. В результате применения метода “разделяй и властвуй” эта оценка снижается до .

            Пусть x и y - два n-разрядных двоичных числа. Для простоты будем считать, что n представляет собой целую степень двойки, т.е. n=2m. Разобьем x и y на две равные части: x=a|b, y=c|d, где a,b,c,d - n/2 -разрядные числа.

            Тогда их произведение можно представить в виде:

x y=(a2n/2 +b) (c2n/2 +d)=ac2n+(ad+bc) 2n/2+bd.  

Это равенство дает способ вычисления произведения x и y с помощью четырех умножений n/2 -разрядных чисел, а также нескольких сложений и сдвигов:

            begin

                        u:=(a+b) (c+d);        v:=ac;           w:=bd;

                        z:=v2n+(u-v-w)  2n/2+w               {*z=xy*}

            end

            Из-за переноса в суммах (a+b) и (c+d) может оказаться (n/2)+1 разрядов. Рассмотрим сначала случай, когда этих разрядов n/2. Тогда временная сложность умножения двух n-разрядных двоичных чисел ограничена сверху функцией:

 

 

Здесь b - это постоянная, отражающая сложение и сдвиги в выражениях, входящих в программу. Решение этого уравнения имеет оценку (см. пример 4.2): .

            Учтем теперь возможность (n/2)+1 разрядов. Для этого запишем сумму a+b в виде a12n/2 +b1, а сумму c+d - в виде c12n/2 +d1. Тогда

u=(a+b) (c+d)= a1 c12n+( a1 d1+ b1c1) 2n/2+ b1 d1.  

            Слагаемое b1 d1 вычисляется с помощью рекурсивного применения этого алгоритма к задаче размера n/2. Остальные умножения можно сделать за время O(n), т.к. они содержат в качестве одного из аргументов либо единичный бит a1 или c1, либо степень числа 2.

            Этот асимптотически быстрый алгоритм можно применить не только к двоичным, но и к десятичным числам.

            Пример. Дано: x=2012, y=3301. Найти: xy.

            Решение.        a=20, b=12, a+b=32;

                                   c=33, d=01, c+d=34;

                                   u=32*34: пусть x0=32, y0=34.

                                                           a0=3, b0=2, a0+b0=5;

                                                           c0=3, d0=4, a0+b0=7;

                                                           u0=5*7=35; v0=3*3=9; w0=2*4=8;

                                                           u=32*34= x0*y0=900+(35-9-8)*10+8=1088;

                                   v=20*33=660;

                                   w=12*01=12;

                                   xy=6600000+(1088-660-12)*100+12=6641612.

            В алгоритме умножения двух n-разрядных двоичных чисел исходная задача размера n имела сложность O(n2). После того, как ее разбили на 3 подзадачи размера n/2, ее сложность снизилась до .

            Вообще, пусть исходная задача размера n имеет сложность O(n2). Разобьем ее на подзадачи, размер каждой из которых равен n/2. Подобное разбиение позволяет улучшить эффективность алгоритма в тех случаях, когда таких подзадач две (в силу примера 4.2 сложность снизится до ) или три (в силу примера 4.2 сложность снизится до ). Если же этих подзадач четыре, то никакого выигрыша мы не получим три (в силу примера 4.2 сложность составит до ). Разбиение на большее количество подзадач размера n/2 просто вредно!

            Пусть теперь исходная задача разбивается на подзадачи, размер каждой из которых равен n/4. Такая процедура имеет смысл, если подзадач окажется не более восьми, т.к. если их девять, то сложность составит . Это означает, что проще было исходную задачу разбить на три подзадачи размера n/2.

 

Балансировка

 

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

            В качестве примера, иллюстрирующего применение метода балансировки при создании эффективного алгоритма, рассмотрим задачу поиска заданного элемента в массиве A[1..n], упорядоченном по неубыванию. Простейший способ решения этой задачи состоит в поочередном сравнении элементов массива с искомым элементом. В “худшем” случае искомый элемент окажется последним или он вовсе не будет найден, поэтому максимальная сложность такого алгоритма T(n)=O(n).

            Вместо того, чтобы разбивать задачу размера n на две подзадачи размера 1 и n-1, следует разбить ее на подзадачи примерно равных размеров. Сравнивая искомый элемент с элементом в середине массива, мы узнаем, в какой половине (левой или правой) следует продолжать поиск. После этого алгоритм рекурсивно применяется к левой и правой части массива до получения массива из одного элемента. Такой алгоритм называется дихотомический поиск.

            Приведенная на рис. 2.2. процедура locate осуществляет дихотомический поиск записи с заданным ключом. Вызов процедуры осуществляется оператором “locate(1,n);”. Логическая переменная b принимает значение true, если искомый элемент в массиве найден.

 

procedure locate(first,last:integer);

var m: integer;

 begin

    if first<last then

       begin

           m:= (first+last) div 2;

           if x<a[m].key then locate(first,m)

           else if x>a[m].key then locate(m+1,last)

                  else {* x=a[m].key *} begin info_x:=a[m].info; b:=true end

        end

    else

       begin if x=a[first].key then begin info_x:=a[first].info; b:=true end end

 end; {*locate*}

 

            Рис. 2.2. Процедура дихотомического поиска.

 

            Полное дерево сравнений, для массива, состоящего из n элементов, содержит ровно n концевых вершин. На рис. 2.3 приведено полное дерево сравнений для массива, имеющего 5

            Рис. 2.3. Дерево сравнений

элементов.     В §8 главы I было доказано, что если бинарное дерево с максимальным количеством вершин имеет n концевых вершин, то его высоту m можно найти по формуле (1.1):

 m=log2(n).

Поскольку полное дерево сравнений не обязательно содержит максимальное количество вершин, то это равенство при больших n выполняется приближенно: m»log2(n). А так как именно высота m определяет максимальную сложность этого алгоритма, то T(n)=O(log2n).

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