Математическая логика и теория алгоритмов

в этой процедуре сравнения происходят только на третьем ша­ ге, где сравниваются два элемента множества S, из которых оно и состоит, и на шаге 7, где сравниваются maxl с тах2 и mini с min2. Пусть Т(п) - число сравнений элементов множества S. Ясно, что- Г(2)=1. Если п>2, то Т(п) - общее число сравнений, произведен­ ных в двух вызовах процедуры MAXMIN (строки 5 и 6), работающих на множествах размера «/2 и еще два сравнения в строке 7. Таким образом, Т(п)=1 еслии = 2; (7.1) [2Т(«/2) + 2, если п>2. Решением рекуррентных уравнений (7.1) служит функция !Г(и)=(3/2)и-2.Таким образом, вместо 2п-2 сравнений получили (312) сравнений чисел, т.е на (п/2) сравнений меньше. Рассмотрим второй пример. Пусть требуется умножить два п разрядных двоичных чисел. При традиционном (школьном) алгоритме требуется 0(«^) битовых операций. Применим стратегию дублирова­ ния и разобьем числа д; на две равные части: а b с d Считаем, что п есть степень числа 2. Тогда xy==(a2"'^+b){c2"4d)=ac2"+{ad+bc)2"4bd. Равенство (7.2) дает способ вычисления ху с помощью четырех умножений (и/2) разрядных чисел и нескольких сложений и сдвигов (умножений на степень числа 2). Можно получить, что вместо О(и^) битовых операций нужно ) к 0(и'''®) битовых операций. Здесь число разбивалось на два блока. Разбивая эти числа на большее число блоков, можно получить, что умножение двух чисел имеет сложность 0(и /og2 « Iog2 log2«) для алгоритма Шёнхаге - Штрассена [2]. 284