(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 8

Пусть а, b и с — неотрицательныепостоянные. Решение рекуррентных уравнений^ (Я)^ ар (и/с) -|-ЙП при и >_ 1 ,где п - степень числа с, имеет вид,Доказательство. Если п — степень числа, тоbge яТ(п)=*Ьпг1, где г —aid.Если а < с, то *=*осходится и, следовательно, Т(п)=0(п).Если а-с, то каждым членом этого ряда будет 1, а всего в немО (log п) членов.

Поэтому Т(п) = 0(п log п). Наконец, если а >с, тоlogertчто составляет0( а ,о«* '») или0( ^ 1ой« й)Из Теоремы 2.5 вытекает, что разбиение задачи размерап (за линейное время) на две подзадачи размера п/2 даеталгоритм сложности Ofnlogn).Ест бы подзадач было 3, 4 или8 , то получился бы алгоритм сложности порядка п 6 , п или псоответственно.С другой стороны, разбиение задачи на 4 задачи размераnl4 дает алгоритм сложности 0(nlogn), а на 9 и 16 - порядкап 0&ъ и п соответственно.

Поэтому асимптотически болеебыстрый алгоритм умножения целых чисел можно было быполучить, если бы удалось так разбить исходные целые числана 4 части, чтобы суметь выразить исходное умножение через8 или менее меньших умножений (см. алгоритм Тоома из (4),стр. 18-20). Верхние оценки порядка роста для рекуррентныхсоотношений см. (4), теорема 2.4.Алгоритм Карацубы для умножения чисел.Этот алгоритм по праву считается первым алгоритмомтипа «разделяй и властвуй». Рассмотрим умножение двух празрядных двоичных чисел. Традиционный метод требует0(п2) операций. Однако в методе, изложенном ниже,достаточно порядка пjoe 3, т.е.

примерно п1 39операции(логарифм выше берётся по основанию 2 ).*ьсdРис. 2.6 Разбиение двоичных чиселПусть х и у - два я-разрядных двоичных числа. Сновабудем считать для простоты, что п есть степень числа 2 .Разобьем х и у на две равные части, как показано на рис. 2.6.Если рассматривать каждую из этих частей как ( п о ­разрядное число, то можно представить произведение чисел хи у в видеху ~ (а2'“4 + 6 ) (с2п^ - 1- d) =— ас2" + (ad 4 - be) 2'1^ -j- fedРавенство выше дает способ вычисления произведения х и у спомощью четырех умножений («/2 )-разрядных чисел инескольких сложений и сдвигов (умножений на степень числа2). Произведение z чисел х н у также можно вычислить последующей программе:beginа ■*— (а 4- Ь)* (с Ч- d );v ч— а * е;w *— h * d;г ч— v -к- 2ft Ч~ (и ~~ о —да) * 2 4 - ДОendНа время забудем, что из-за переноса а+b и c+d могутиметь (п/2)+\ разрядов и предположим, что они состоят лишьиз п/2 разрядов.

Наша схема для умножения двух «-разрядныхчисел требует только трех умножений (и/2 )-разрядных чисел инескольких сложений и сдвигов. Длявычисленияпроизведений и, v и w можно применять программу вышерекурсивно. Сложения и сдвиги занимают 0(п) времени.Следовательно, временная сложность умножения двух празрядных чисел ограничена сверху функциейI It(п) ~ |(П/ 2 )при » = I,kn при п > 1 ,где к - постоянная, отражающая сложение и сдвиги ввыражениях из программы. Решение рекуррентных уравненийвыше ограничено сверху функцией 3knlog3 » 3кп'59. На самомделе можно показать, что Т(и) - 3кпщЪ- 2кп.Доказательство этого факта проведем индукцией по п,где п - степень числа 2.

Базис, т. е. случай п=\, тривиален.Если функция Т(н) = 3knlog3 - 2кп удовлетворяет системе вышепри п=?п, то7’(2т) = 37’ (тН -2йт™■=* 3 [3kmh>;8— 2kin] - f 2km =■~3k(2in)los 3~'2k (2m),так что она удовлетворяет этой системе и при п=2т. Отсюдаследует, что 7(п) < 3knlog3. Заметим, что попытка использоватьв индукции 3кп°8Ъвместо Зкп°кЪ- 2кп не проходит.Для завершении описания алгоритма умножения мыдолжны учесть, что числа а+Ъ и c+cl, вообще говоря, имеют(л/2 ) + 1 разрядов и поэтому произведение (a+b)(c+d) нельзявычислить непосредственным рекурсивным применениемнашего алгоритма к задаче размера п/2. Вместо этого надозаписать а+b в виде а{2!'12+Ьъ где ах=0 или 1.

Аналогичнозапишем c+d в виде Ci2"a +a'1. Тогда произведение (a+b)(c+d)можно представить в видеЙ,Р,2“ ++ V ,) 2 ' , / 5 +■Слагаемое bxdxвычисляется с помощью рекурсивного применения нашегоалгоритма умножения к задаче размера п!2. Остальныеумножения в последнем выражении можно сделать за времяО(н), поскольку они содержат в качестве одного из аргументовлибо единственный бит ах или сь либо степень числа 2 .Пример.Асимптотическибыстрыйалгоритмумножения целых чисел Карацубы можно применять нетолько к двоичным, но и к десятичным числам.Проиллюстрируем это на примере:*-3 14 1ij *»5927а =>31i>=41с -6 9(1=27а+Ь = Пи = ( « + & ) {с+ d) = 7 2 x 3 6 = 6192c+d^mу «с = 3! -X 69 ®> 1829M > = W « 4 ! X 2 7 = 11Q7хд -18290000') + ( 6 1 9 2 - 1 8 2 9 - 1 1 0 7 ) X 1 0 0 + 1 1 0 7 * 18616707.') число и следует сдвинуть на четыре десятичных разряда, а и -и -w - на два.Заметим, что наш алгоритм заменял одно умножениетремя сложениями и вычитанием.

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

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

В заключение данной Главы приведём рядупражнений.УПРАЖНЕНИЯ1. Напишите алгоритм для обращения порядка элементов всписке, докажите, что он работает правильно и оцените егосложность.*2. Задача об устойчивом бракосочетании. Пусть В множество из и юношей, a G — множество из п девушек.Каждый юноша оценивает девушек числами от 1 до и, икаждая девушка оценивает юношей числами от 1 до п.Паросочетаниемназываетсявзаимнооднозначноесоответствие между юношами и девушками.

Паросочетаниеустойчиво, если для любых двух юношей Ь\ и Ь2 исоответствующих им в этом паросочетании девушек g\ и g2выполняются следующие два условия:1 ) либо Ъ\ оценивает gj выше, чем g2, либо g2 оценивает Ь2выше, чем Ъ\,2) либо Ъ2 оценивает g2 выше, чем g b либо g\ оценивает Ъ\выше, чем Ъ2.Докажите, что устойчивое паросочетание всегда существует инапишите алгоритм для нахождения одного из такихпаросочетаний.*3. Ханойские башни.

Имеются три стержня А, В и С и пдисков разных размеров. Вначале все диски нанизаны настержень А в порядке убывания размеров, так что наибольшийдиск находится внизу. Надо так переместить диски со стержняА на стержень В, чтобы никакой больший диск ни разу неоказался над меньшим; за один шаг можно перемещать толькоодин диск. Стержень С можно использовать для временногохранения дисков.

Напишите рекурсивный алгоритм решенияэтой задачи. Каково время работы вашего алгоритма втерминах числа перемещений дисков?*4. Докажите, что для решении упр. 3 необходимо идостаточно 2 ” - 1 перемещений.5. Напишите алгоритм порождения всех перестановок целыхчисел от 1 до п.

Указание: множество перестановок целыхчисел от 1 до и можно получить из множества перестановокцелых чисел от 1 до п-1 , вставляя все возможные позиции вкаждой перестановке.6 . Решите следующие рекуррентные уравнения, считая, чтоТ(и)=1:Т(и)=а-Т(и-1)+Ьп;Т(п)-а -Т(п-1)+Ьп'\7(n)=a-7(n/2)+bnlogn;7(n)=a-T(n/2)+bn .7. Покажите, что для одновременного нахождениянаибольшего и наименьшего элементов и-элементногомножества необходимо и достаточно Г(3/2)и-21 сравнений.8 .Модифицируйте алгоритм умножения целых чисел спомощью разбиения каждого целого числа на(а) три и(б) четыре части. Какова сложность получаемых алгоритмов?9.

Пусть Я-массив размера п, состоящий из целых чисел,данных в порядке возрастания (числа различны и не равны 0 ).Написать алгоритм нахождения числа i такого, что A,=i (еслитакое существует). Докажите, что 0(logn) - наилучшийвозможный порядок.10. Показать, что решением рекуррентного уравнения А(1)=1,Х(п)= £ X(i)X(i-1) для п> 1 служит Ди+1)= [1/(и+1)] С2„” .;=JЗдесь Х(п) - число способов правильной расстановки скобок вцепочке из п символов (числа Каталана). Докажите, что Х(п) >2 "'2.ГЛАВА 3. НЕДЕТЕРМИНИРОВАННЫЕ ВЫЧИСЛЕНИЯИ КЛАСС ЗАДАЧ NPТеперь введём второй важный класс языков (задачраспознавания свойств) - класс NP (см. также (1)). Прежде чемперейти к формальному определению в терминах языков имашин Тьюринга, полезно пояснить смысл понятия, лежащегов основе определения класса NP.Рассмотрим задачу КОММИВОЯЖЕР, описание которойприведено в начале настоящей главы.