§ 27. Добавление нулей 179

выполненное в случае m = s^k, fceN, и равенство

r«(m) = rW(s'l⁰&ml)_J

выполненное при произвольном meN⁺, приводят к оценке Т^(т) = = 0(m^logs(2s-^i:)) для битовой сложности алгоритма, использующего разбиение на s частей. Может быть также показано, что

r^(s)(m) = e(m^log»^(2s-¹⁾). (27.14)

Очевидно,

log_s(2s - 1) = log_s 2s(l - ^) = 1 + log_s 2 + log_s(l - ^) •

Отсюда

limlog,(2s-l) = l.

Это означает, что для любого е > О можно найти целое s ^ 2 такое, что умножение Тоома с разделением на s частей (битовая длина числа предполагается равной s^k, fceN) будет иметь битовую сложность, до­пускающую оценку 6(т¹⁺⁵) при некотором 5 таком, что 0 < 5 ^ е; ра­зумеется, для битовой сложности этого алгоритма справедлива оцен­ка 0(.т¹⁺П.

Скажем коротко об основной идее алгоритма Тоома, приводящей к неравенству (27.13). Если, как предполагалось, битовая длина каж­дого из сомножителей а,Ъ есть s^k, fceN, то последовательность дво­ичных цифр каждого из сомножителей а, Ъ можно разбить на s групп по s^-1 цифр:

а₃-ъ ■■■> ai> ^ао> b_s-₁, ...,Ь_г,Ъ₀. Сами сомножители а, Ъ суть значения полиномов

А(х) = а_-х"-¹ + ...+_а1х + а₀, В(х) = Ь_-х*^-1 + ... + Ъ_гх + Ъ₀

в точке х₀ = 2^s*^-1. Полином С(х), равный произведению А(х)В(х), есть полином степени не выше чем 2s - 2 (мы не утверждаем, что эта степень равна 2s - 2, так как возможно, что к изначально заданным целочисленным сомножителям спереди дописывались нули), и доста­точно знать значения С (х) в 2s- 1 точках (узлах интерполяции) для того, чтобы затем, например, с помощью интерполяционной форму­лы Лагранжа найти значение

СС2**-¹), (27.15)

180 Глава 6. Рекуррентные соотношения и сложность алгоритмов

равное ab. Тоом показал, что если в качестве узлов интерполяции x_ъ x₂,..., x_2s-i взять числа

-(s-l),-(s-2),...,-l,0,1, ...,s-2,s-l,

рекурсивно с помощью рассматриваемого алгоритма найти

A(x_i\ B{xi), C{x_i)=A{x_i)B{x_i), i = l,2,...,2s-l,

и затем, пользуясь интерполяционной формулой Лагранжа, найти значение (27.15), то это приведет к (27.13), (27.14). Такое использова­ние интерполяции заключает в себе требуемое обобщение алгоритма Карацубы.

В 1972 г. Шенхаге и Штрассен, основываясь на идее Тоома исполь­зования интерполяции полиномов в алгоритмах умножения целых чисел, получили алгоритм умножения, битовая сложность которого допускает оценку O{m log m log log m), мы уже упоминали этот алго­ритм в §21. Функция m log m log log m растет медленнее, чем m¹⁺⁵ при любом 5 > 0. Улучшение достигнуто за счет привлечения интер­поляции специального вида — так называемого быстрого преобразо­вания Фурье^г. До настоящего времени результат Шенхаге—Штрассе-на остается рекордным. Шенхаге на основе этого алгоритма умноже­ния предложил алгоритм² нахождения нод(a₀,a_г), сложность кото­рого допускает оценку O{m log² m log log m), где m — битовая длина большего числа a₀ (в примере 21.2 было показано, что алгоритм Ев­клида имеет сложность Θ(m²)).

Необходимо сказать, что преимущества по времени выполнения рассмотренных алгоритмов перед наивным умножением и алгорит­мом Евклида проявляются лишь при очень больших значениях m.

С умножением матриц положение таково, что обобщения алгорит­ма Штрассена в духе обобщения, предложенного Тоомом для алгорит­ма Карацубы, до сих пор не найдено. Используя другие идеи, Д. Коп-персмит и С. Виноград в 1987 г. предложили алгоритм со сложностью O(n^2,376), где n—порядок перемножаемых квадратных матриц³. Этот результат остается рекордным по сей день. Существует ли для любо­го s > 0 алгоритм умножения матриц со сложностью O{n^2+е)—это открытый вопрос.

Об алгоритме Шенхаге—Штрассена см., например, [5, разд. 7.5]. См., например, [5, разд. 8.10]. См. [47].

Задачи

181

Задачи

122. Игра «Ханойские башни». К горизонтальной доске приделаны три вертикальных столбика. На первый нанизано n дисков, диамет­ры которых убывают вверх (рис. 21). Требуется, перекладывая диски

V/////A

V/////////A

V///////////A

///////////A

/////

/////

Рис. 21. Игра «Ханойские башни». Исходное положение.

по ке.

одному, расположить их в прежнем порядке на третьем столби-

Ограничение состоит в том, что больший диск никогда не может располагаться над меньшим. Разработать рекурсивный алгоритм ре­шения этой задачи и определить его временную сложность по числу перекладываний дисков.

123. (Продолжение предыдущей задачи.) Требуется определить временную сложность алгоритма перекладывания дисков в игре «Ха­нойские башни» при условии, что затраты на перекладывание со столбика на столбик i-го по величине диска равна а) i; б) i²; в) У.

Y2A. Сформулировать правило нахождения частного решения ре­куррентного уравнения a_dy{n) + a_d-_iy{n - 1) + ... + a₀y(.n - d) = f(n) для случая, когда f(n) принимает постоянное значение c.

125. Пусть функция f(n) определена для всех n е N+ и пусть a — ненулевое число. Любое определенное для всех neN решение рекуррентного уравнения y(n) - ay{n - 1) =f(n) имеет вид y(n) =

f(k) a^k

ⁿ

= an(y(0) + 2

Указание. Индукция по n.

k=i

\1Ь. Для чисел Фибоначчи выполнено равенство £ F_i = F_n+2 - 1,

n= 1,2,3,

i = l

Указание. Решением рекуррентного уравнения y(n)- y(n - 1)= F_n, y(0) 1, является y(n)= F_n+2.

182 Глава 6. Рекуррентные соотношения и сложность алгоритмов

127. Верно ли, что для любого полинома р{п) найдется полином q{n) (оба с вещественными коэффициентами) такой, что q(n + l)-— q{n) =р{п), и если да, то как различаются степени полиномов р{п) и q{n)?

127. Найти множество всех вещественных последовательностей, удовлетворяющих рекуррентному уравнению у(п + 1) + у{п) = 0.

127. Вернемся к алгоритму V_Rec из § 24. Пусть 1 s= k s= п. Сколько раз при построении множества V_n будет выполнено построение мно­жества V_k?

Ответ. F_n__k.

130. Найти общее решение рекуррентного равенства (24.11) при к = 1. Найти частное решение, удовлетворяющее условию у(0) = 0. (При к = 1 рекурсия (24.10) не приводит к избыточным вычислениям значений U.)

130. Назовем перестановку г_ъг₂, ...,z„ чисел 1, ...,п критической длины п, если на ней достигается максимум числа сравнений, тре­буемых рекурсивной сортировкой слияниями для массивов длины п. Пусть п > 1, а х_ъ ...,X|n/2j и Уг> ■■■>У\п/2\ суть некоторые критические перестановки длины ^ и ^ . Тогда числа z₁,z₂, ■■■,z_n, равные, со­ответственно,

2х_ъ ..., 2x_Ln/2J, 2у_г - 1,..., 2у_[п/21 - 1

образуют критическую перестановку длины п (рис. 22).

1

Рис. 22. Случай, когда при п = 7 для сортировки слияниями потребуется мак­симальное число сравнений.

132. Как выглядят критические перестановки длины 6, 7, 8 и 9, по­лученные с помощью предложенного в предыдущей задаче подхода?

Задачи

183

133. Имеет место равенство (25.16). Указание. См. задачу 131.

134. (Продолжение задачи 131, в которой фактически в рекурсив­ной форме описан алгоритм построения некоторой критической пе­рестановки длины п.) Исследовать сложности описанного алгоритма построения некоторой критической перестановки длины п по чис­лу умножений на два и по числу вычитаний единицы. Предложить нерекурсивный алгоритм (например, можно рассмотреть последова­тельное построение критических перестановок, длины которых суть соответственно 1, 2,..., п) и исследовать его сложности по названным операциям.

134. Чему равно наименьшее п вида 2^к, для которого число срав­нений при рекурсивной сортировке слияниями превосходит [log₂ nil?

134. Оценка (25.22) является следствием оценки T_RS(n) = A(n) + + А*(п)-2.

134. Для сложности алгоритма бинарного поиска места элемента в упорядоченном массиве обосновать рекуррентное неравенство

( 1, еслип = 1,

TnsM^ г\п\Л

tbsIIj\)+1> еслип>1,

не прибегая к известному явному выражению для T_BS(n). Из этого рекуррентного неравенства получить оценку для T_BS(n).

138. Указать алгоритм построения пересечения п полуплоскостей

щх + Цу + с^О, i = l, 2,..., п,

имеющий временную сложность G(nlogn) по общему числу опе­раций.

Указание. Пересечением будет выпуклый многоугольник (возможно, не­ограниченный). Опираясь на алгоритм Шеймоса—Хоя (задача 14), использо­вать стратегию «разделяй и властвуй».

139. По сравнению с теоремами 26.1, 26.2 предложения 25.1, 25.2 представляют собой более сильные утверждения, имеющие к тому же более широкое применение. Используя эти предложения, получить асимптотические оценки для

(О, если п = 1,

Kill) +K\l]) +^LP^' еслип>1, при If (П) = l0g₂ П и If (n) = n log₂ n.

184 Глава 6. Рекуррентные соотношения и сложность алгоритмов

140. Рекуррентное неравенство вида (26.1) может иметь более од­ного решения, однако во всех трех случаях, предусмотренных фор­мулой (26.2), по крайней мере для одного решения соответствующая оценка из (26.2) является точной.

140. Обобщить предложенную в этой главе технику решения ре­куррентных неравенств на случай, когда задача с размером входа п

разбивается на s задач, размер каждой из которых — это - или

- , где s — некоторое натуральное число ^2. Как будут выглядеть теоремы 26.1, 26.2 в этом случае?

142. Доказать соотношение (27.10).

Указание. Рассмотреть количество умножений чисел битовой длины 1 в процессе применения алгоритма Карацубы к входу размера т и показать, что G(m) является для него нижней оценкой.

143. а) Для любого е > 0 можно указать JV > 0 такое, что ЗГ_км(т) < < Г_км(2т) < (3 + е)Т_км(т) при всех т ^ N.

б) Для любого е>0 можно указать JV > 0 такое, что 7T_St(n) < <r_St(2n)<(7 + e)T_St(n) при всех n^N.

Указание. См. (27.10), (27.8) и, соответственно, (27.12).

144. Теоремы о рекуррентных неравенствах часто формулируются иначе. Например, в [4] и [5] теорема дается, с точностью до обо­ значений и используемых слов, в следующем виде. Пусть s — целое ^ 2, и при любом п вида s^k, k = 1, 2, ..., вещественная функция /(п) натурального аргумента удовлетворяет неравенству

f(n)^wf(-) +cn^d, s

где w,c,d — константы, причем w > 0, о 0, d ^ 0. Пусть при этом /(п) не убывает на каждом отрезке [s^ + l.s*]. Тогда

(o(n^d log n), еслиd = log_sw,

f(n) = \0{n^d), еслиd>log_sw,

[о(п^1о&^№), еслиd<log_sw.

Доказать эту теорему. (Заметим, что в условии теоремы 26.1 нет тре­бования неубывания /(п) на каждом отрезке [s^k + l,s^k], но зато тре­буется, чтобы, например, неравенство (26.1) выполнялось для всех п, а не только для п вида 2^fc.)