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

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

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

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

(Ь при =п1,

\аТ(п/с)+Ьп при п>\, еде п - степень числа с, имеет вид,

О (п), если а<с.

Т{п)

O(nlogrt), если а = с, О (nosc), если а>с.

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

T(n) = bn 2 где г = а/с.

(Х>

Если а<о, то Уг сходится и, следовательно, Т(,п)=0{п).

Если а=с, то каждым членом этого ряда будет 1, а всего в нем О (log п) членов. Поэтому Т{п)=0{п log п). Наконец, если а>с, то

= bn

bn X

что составляет 0(a°8c"), или 0(n°8ca). q

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



2.7. БАЛАНСИРОВКА

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

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

2.7. БАЛАНСИРОВКА

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

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

Этот алгоритм приводит к рекуррентным уравнениям

гг. i о при п=1,

(«)=(г(п-1)+п-1 прип>1 (2.7)



ДЛЯ числа сравнений, произведенных между сортируемыми элементами. Решением для (2.7) служит Т (п)=п{п-1)/2, что составляет 0(rt»).

Хотя этот алгоритм можно считать рекурсивным применением приема "разделяй и властвуй" с разбиением задачи на неравные части, он не эффективен для больших п. Для разработки асимптотически эффективного алгоритма сортировки надо позаботиться о сбалансированности. Вместо того чтобы разбивать задачу размера п на две подзадачи, одна из которых имеет размер 1, а другая - размер п-1, надо разбить ее на две подзадачи с размерами примерно п/2. Это выполняется методом, известным как сортировка слиянием.

Рассмотрим последовательность целых чисел Хи Хг, . . . , х„. Снова предположим для простоты, что п есть степень числа 2. Один из способов упорядочить эту последовательность - разбить ее на две подпоследовательности Xi, Хз, ... , Xn/t и Х(пм + 1.....Хп, упорядочить каждую из них и затем слить их. Под "слиянием" мы понимаем объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.

Алгоритм 2.4. Сортировка слиянием

Вход. Последовательность чисел Хи х....., Хп, где п - степень

числа 2.

Выход. Последовательность уи «/»,..., «/„, являющаяся перестановкой входа и удовлетворяющая неравенствам .

Метод. Применим процедуру СЛИЯНИЕ(5, Т), входом которой служат две упорядоченные последовательности S и 7", а выходом - последовательность элементов из S и Т, расположенных в порядке неубывания. Поскольку S н Т сами упорядочены, СЛИЯНИЕ требует сравнений не больше, чем сумма длин S и Г без единицы. Работа этой процедуры состоит в выборе большего из наибольших элементов, остающихся в S и Г, и в последующем удалении выбранного элемента. В случае совпадения можно отдавать предпочтение последовательности S.

procedure COPT(t, /): if t = / tlien retui Xi else begin

m(i + j-l)/2;

return СЛИЯНИЕ(С0РТ(1, m), COPT(m+l, /))

Рис. 2.14. Сортировка слиянием.





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.0039