Лекция: Pair value, value1, value2;

if ((size)==2) h6

{

if (*in_min < *in_max) 31

{

value.max=*in_max;

value.min=*in_min;

} else

{

value.max=*in_min;

value.min=*in_max;

}

return value;

} else

{

size1=size>>1; // Уменьшение размера массива вдвое

in_min1=in_min; in_max2=in_max; // Указатели на крайние элементы двух

in_max1=in_max-size1; in_min2=in_min1+size1; // новых массивов, составляющих исходный

value1=Max_Min(array, size1, in_min1, in_max1); h4

value2=Max_Min(array, size1, in_min2, in_max2); h5

if (value1.max < value2.max) value.max=value2.max; 32// Вместо этих операторов для массива

else value.max=value1.max; // int можно использовать библиотечные

if (value1.min < value2.min) value.min=value1.min; 33//функции max и min языка C++, что

else value.min=value2.min; // делает программу более изящной

return value;

}

} // Конец Max_Min

Вместо предпоследних четырёх строк функции Max_Min перед оператором return value можно воспользоваться библиотечными функциями из stdlib.h Borland C++

value.max=max(value1.max, value2.max); value.min=min(value1.min, value2.min),

что сделает код программы более изящным, но если тип массива будет не int, то эти строки должны остаться без изменений. Структура pair введена для удобства записи кода программы.

Легко заметить, что сравнения элементов множества S происходят только в строках 1, 2, 3, помеченных символом 3. Пусть C(n) — число сравнений элементов множества S, которые надо произвести в процедуре MaxMin, чтобы найти наибольший и наименьший элементы множества S. Ясно, что C(2)=1. Если n >2, то C(n) — общее число сравнений, произведенных в двух вызовах функции MaxMin (строки h4 и h5), для множеств размера n/2, и ещё два сравнения в строках32 и 33. Следовательно:

(1.4)

Решением рекуррентных уравнений (1.4) является функция C(n)= n–2. Это легко доказать по индукции. Очевидно, что при n=2 эта функция удовлетворяет (1.4). Предположим, что при n=m³ 2 данная функция тоже является решением (1.4). Тогда

C(2m) = 2 + 2 = (2m) — 2,

т.е. функция C(n) удовлетворяет (1.4) при следующем значенииn=2m. Значит, еслиn является степенью числа 2, то выбранная функция удовлетворяет рекуррентному соотношению (1.4).

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

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

Рассмотрим теперь другой пример, где удается даже понизить порядок роста сложности алгоритма. Пусть требуется умножить два n-разрядных двоичных числа. Традиционный метод требует O(n2) битовых операций. В методе, излагаемом ниже, достаточно уже порядка nlog3 (где логарифм берется по основанию 2), т.е. примерно n1,59 битовых операций.

Пусть x и y — два n-разрядных двоичных числа. Для простоты n опять будет степенью числа 2. Разобьём x и y на две равные части, как показано на рисунке 9. Если рассматривать каждую их этих частей как (n/2)-разрядное число, то можно представить произведение чисел x и y в виде

x×y = (a×2n/2 + b)(c×2n/2 +d) = a×c×2n + (a×d + b×c)×2n/2 + b×d (1.5)

Равенство (1.5) даёт способ вычисления произведения x на y с помощью четырех умножений (n/2)-разрядных чисел и нескольких сложений и сдвигов (умножений на степень числа 2).

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

Произведение z чисел x и y можно вычислить по программе, основным фрагментом которой является следующий.

// Программа 5 расчёта произведения двух двоичных чисел

{

u=(a+b)*(c+d);

v=a*c;

w=b*d;

z=v<<n+(u-w-v)<<(n>>1)+w;

}

Не будем пока учитывать, что из-за возможного переноса разрядов суммы a+b и c+d могут иметь n/2+1 разрядов, и предположим, что они состоят лишь из n/2 разрядов. Предложенная схема умножения двух n-разрядных чисел требует только трёх умножений (n/2)-разрядных чисел и нескольких сложений и сдвигов. Для вычисления произведений u, v, и w можно применять эту программу рекурсивно. Сложения и сдвиги занимают обычно O(n) времени. Следовательно, временная сложность умножения двух n-разрядных чисел ограничена сверху функцией:

(1.6)

где k — постоянная, отражающая временные затраты при сдвигах и сложениях в (1.5). Решение рекуррентных уравнений (1.6) задается функцией:

C(n) = 3×k×nlog3– 2×k×n.

Доказательство можно провести по индукции. Случай, когда степень числа 2 n=1, тривиален. Пусть теперь n=m, и функция C(n) = 3×k×mlog3– 2×k×m удовлетворяет (1.6). Тогда при n=2×m:

C(2m) = 3 C(m) + 2×k×m = 3×[3×k×mlog3– 2×k×m] + k×(2m) = 3×k×(2m)log3– 2×k×(2m),

она тоже удовлетворяет (1.6). Отсюда следует, что C(n) £ 3×k×nlog3.

Для завершения описания алгоритма умножения необходимо учесть, что числа a+b и c+d, вообще говоря, имеют n/2+1 разрядов. Поэтому произведение (a+b)(c+d) нельзя вычислить непосредственным рекурсивным применением приведенного алгоритма к задаче размера n/2. Вместо этого надо записать a+b в виде a1×2n/2+b1, где a1=0 или1. Аналогично c+d запишем в виде c1×2n/2+d1. Тогда произведение (a+b)(c+d) можно переписать в виде:

a1×c1×2n + (a1×d1 + b1×c1)×2n/2 + b1×d1 (1.7)

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

Пример 1.6.Этот асимптотически быстрый алгоритм умножения целых чисел можно применять не только к двоичным, но и к десятичным числам. Пусть надо умножить два целых числа x=3141 и y=5927. Тогда:

a = 31

b = 41

a + b = 72

c = 59

d = 27

c + d = 86

В соответствии с алгоритмом программы 5 требуется выполнить три умножения двузначных чисел:

 u = (a + b)×(c + d) ‚ v = a×c ƒ w = b×d

Выполним их последовательно, применяя рекурсивный алгоритм для однозначных чисел:

 u = (a + b)×(c + d) = 72×86

a0= 7, b0= 2, c0= 8, d0= 6;

Далее:

a0 + b0= 9 = a1´10 + b1, Þ a1= 0, b1= 9;

c0+ d0= 14 = c1´10 + d1, Þ c1= 1, d1= 4;

В соответствии с (1.7):

u0= a1× c1´102+ (a1×d1+ c1×b1)´10 + b1×d1= 0 + 90 + 36 =126;

v0= a0×c0= 56, w0= b0×d0= 12.

Тогда из (1.5):

u = (a + b)×(c + d) = v0´102 + (u0-v0-w0) ´10 + w0= 5600 + (126 – 56 – 12)´10 + 12 = 6192.

Аналогично подсчитываются и остальные два произведения:

‚ v = a×c = 31×59 = 1829,

ƒ w = b×d = 41×27 = 1107.

Окончательно из (1.5):

x×y = v´104 + (u – v — w) ´102+ w = 18290000 + (6192 – 1829 – 1107)´102+ 1107 = 18616707.

Если бы умножение четырёхзначных чисел x и y проводить стандартным способом, то потребовалось бы 16 умножений однозначных чисел и 20 сложений. В рассмотренном примере потребовалось 9 умножений, 45 сложений и 8 сдвигов.ð

Алгоритм, основанный на преобразовании (1.5), не является более быстрым по сравнению с обычным умножением x×y. Это видно из (1.5) — одно умножение n-разрядных чисел заменяется 4-мя умножениями (n/2)-разрядных чисел. Но, метод программирования выражения (1.5), заложенный в программу 5, позволяет заменить одно из этих умножений (n/2)-разряд­ных чисел и сложение n-разрядных чисел двумя сложениями и вычитаниями (n/2)-разрядных чисел. Почему такая замена приводит к асимптотической эффективности? Интуитивно это можно объяснить тем, что умножение выполнить труднее, чем сложение, и для достаточно больших n любое фиксированное число n-разрядных сложений требует времени меньше, чем n-разрядное умножение, независимо от того, какой из (известных) алгоритмов применяется. Может показаться, что уменьшение числа (n/2)-разрядных произведений с четырёх до трёх может уменьшить общее время в лучшем случае на 25 %. Однако соотношения типа (1.5) применяются рекурсивно для вычисления (n/2)- разрядных, (n/4)-разрядных и т.д. произведений. Эти 25-процентные уменьшения объединяются и дают в результате асимптотическое улучшение временной сложности.

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

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

где n — степень числа c, имеют вид:

(1.8)

Доказательство. Если n — степень числа c (т.е. n=1, c, c2 и т.д.), то легко проверить непосредственной подстановкой, что ряд

удовлетворяет условию теоремы. Пусть теперь a<c, тогда ряд в последнем равенстве сходится, и, следовательно, C(n) = O(n). Если a=c, то каждым членом ряда будет 1, а всего в нём O(logn) членов. Поэтому C(n) = O(n× logn). Наконец, если a>c, то

,

что составляет O(aq), или O(nr), где r=logca.ð

Из теоремы 1 вытекает, что разбиение задачи размера n (за линейное время) на две подзадачи размера n/2 даёт алгоритм сложности O(n×logn). Если бы подзадач было 3, 4 или 8, то получился бы алгоритм сложности порядка nlog3, n2 или n3 соответственно. С другой стороны, разбиение задачи на 4 подзадачи размера n/2 даёт алгоритм сложности O(n×logn), а на 9 и 16 — порядка nlog3 и n2 соответственно. Поэтому асимптотически более быстрый алгоритм умножения целых чисел можно было бы получить, если бы удалось так разбить исходные целые числа на 4 части, чтобы суметь выразить исходное умножение через 8 или менее меньших умножений.

Если n не является степенью числа c, то обычно можно вложить задачу размера n в задачу размера m, где m — наименьшая степень числа c, большая или равная n. Поэтому порядки роста, указанные в теореме 1, сохраняются для любого n.

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

В обоих примерах на технику “разделяй и властвуй” задача разбивалась на две подзадачи равных размеров. Это не было случайностью. Поддержание равновесия — основной руководящий принцип при разработке хорошего алгоритма. Для иллюстрации этого принципа рассмотрим пример из сортировки и сопоставим эффекты от разбиения задачи на подзадачи неравных размеров и подзадачи равных размеров. Но из этого примера не следует делать скоропалительный вывод о том, что балансировка (balancing) полезна только для техники “разде­ляй и властвуй”. В последующих разделах будут приведены примеры применения балансировки для решения других задач.

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

(1.9)

для числа сравнений, произведённых между сортируемыми элементами. Решением для (1.9) будет C(n)=n×(n-1)/2, что составляет O(n2).

Хотя это алгоритм можно считать рекурсивным применением приёма “разделяй и властвуй” с разбиением задачи на неравные части, он не эффективен для больших n. Для разработки асимптотически эффективного алгоритма сортировки надо позаботиться о сбалансированности. Вместо того чтобы разбивать задачу размера n на две подзадачи, одна из которых имеет размер 1, а другая — размер n-1, надо разбить её на две подзадачи с размерами примерно n/2. Это выполняется методом, известным под именем сортировка слиянием (merge sorting).

Рассмотрим последовательность целых чисел x1, x2, …, xn. Пусть для простоты опять n есть степень числа 2. Один из способов упорядочить эту последовательность – разбить её на две подпоследовательности x1, x2, …, xn/2 и x(n/2)+1, x(n/2)+2, …, xn, упорядочить каждую из них и затем слить их. Под «слиянием» здесь понимается объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.