Главная Промышленная автоматика.

procedure MAXMIN(S):

1. if 15 = 2 then

begin

2. пусть S = {a, b};

3. return (MAX(a, b), MIN(a, b)) end

else begin

4. разбить 5 на два равных подмножества и 5,;

5. (maxl, mini) -MAXMIN(Si);

6. (max2. min2) -MAXMIN(S,);

7. return (MAX(maxl, max2), MIN(minl, min2))

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

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

j 1 при ге = 2,

Т{п)=<у („/2) = 2 при п > 2. (2.2)

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

Г(2т) = 2(--2)4-2 = -(2т)-2,

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

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

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

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



(2.3)

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

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

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

ху = (а2"/2 +Ь) (c2"/» -f d) == = ас2" + {ad + be) 2"/ + bd.

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

begin

«(a + 6)*(c+d); у <-а* с; w"-

2 D * 2" + (ы-у - ay) * 2"/а a,

На время забудем, что из-за переноса а-\-Ь и c+d могут иметь n/2+l разрядов, и предположим, что они состоят лишь из п/2 разрядов. Наша схема для умножения двух п-разрядных чисел требует только трех умножений (п/2)-разрядных чисел и нескольких сложений и сдвигов. Для вычисления произведений ы, у и ш можно применять эту программу рекурсивно. Сложения и сдвиги занимают Об(п) времени. Следовательно, временная сложность умножения двух п-разрядных чисел ограничена сверху функцией

( k при п = 1,

" = \ЗГ(п/2)+/гп при п>1,

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

1) Напомним, что, если не оговорено противное, все логарифмы в этой книге берутся по основанию 2,

(2.4)



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

Г(п) = 3/гп°8з 2/гп.

Доказательство проведем индукцией по п, где п - степень числа 2. Базис, т. е. случай п=\, тривиален. Если функция Т{п)~ =3йге°-2kn удовлетворяет (2.5) при п=т, то

T{2m) = 3T(m) + 2km =

= 3 {3km => - 2km] + 2km = = 3/2 {2my°s - 2k {2m),

так что она удовлетворяет (2.5) и при п=2т. Отсюда следует, что T(nXЗre°s Заметим, что попытка использовать в индукции 3fe«°s вместо 3kn}°-2kn не проходит.

Для завершения описания алгоритма умножения мы должны учесть, что числа а+Ь и c+d, вообще говоря, имеют п/2+\ разрядов, и поэтому произведение {a+b){c+d) нельзя вычислить непосредственным рекурсивным применением нашего алгоритма к задаче размера п/2. Вместо этого надо записать а+Ь в виде ai2"/2+6i, где ai=0 или 1. Аналогично запишем c+d в виде Ci2"/2-t-di. Тогда произведение {a+b){c+d) можно представить в виде

ал2« + (a,d, + b,c,) 2"/ + b,d,. (2.6)

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

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

л; = 3141 а = 31 с = 59

(/«5927 й = 41 d = 27

0+6 = 72 c + d = 86 u = {a + b) (c + d) = 72x86 = 6192 u = ac = 31 x59= 1829 tt) = M = 41x27=1107 = 182900001) +(6192-1829-1107) x 100 + 1107= 18616707. □

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

) Число v следует сдвинуть на четыре десятичных разряда, а и-v-w - на

два.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 [22] 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002