§ 17. Сложность алгоритмов, использующих рекурсию

1°. Рекурсия является важным и очень общим алгоритмическим приемом для построения эффективных алгоритмов. Данный прием заключается в решении задачи путем сведения ее к одной или нескольким подзадачам за счет разбиения исходной задачи. Используя рекурсию, часто можно достаточно просто представить и записать алгоритмы. Многие языки программирования (Алгол, PL/1, Паскаль, но не ФОРТРАН) допускают рекурсивные процедуры. Для многих практически важных задач лучшие оценки сложности дают алгоритмы, использующие рекурсию. Рассмотрим несколько примеров.

1. Сортировка чисел. Дана последовательность x1, x2,..., xn натуральных

чисел. Требуется путем попарных сравнений чисел упорядочить ее, т.е. представить в виде

			xi	, xi	,..., xi ,	(1)
			1	2	n
причем	xi	≤ xi ≤ ...	≤ xi .
	1	2		n

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

данный шаг. Легко видеть, что такой алгоритм требует O(n2 ) попарных сравнений в худшем случае. Предложим для данной задачи рекурсивный

алгоритм. Пусть n=2k .

При k=1 алгоритм упорядочивает последовательность одним сравнением. Пусть для k алгоритм определен. Тогда при k +1 алгоритм работает так:

1.Последовательность x1, x2,..., x2k+1 разбивается на две длины 2k : x1, x2,..., x2k и x2k +1,..., x2k+1 .

2.К обеим последовательностям длины 2k применяется построенный алгоритм и получаем две упорядоченные последовательности: x1′, x2′,..., x2′k и

x2′k +1,..., x2′k+1 .

3. Осуществляется слияние двух полученных упорядоченных последовательностей сравнением их наименьших элементов x1′ и x2′k +1 и

помещением наименьшего в начало результирующей последовательности.

Пусть n ≠ 2k . Тогда последовательность дополняется нулями, так, чтобы ее длина стала степенью двойки.

Пусть Т(n) - число попарных сравнений, используемых в данном алгоритме для произвольной последовательности длины n. Тогда получаем соотношение

n			+ n −1
Т(n)=2T				(2)
	2

T(2)=1.

108

Утверждение 1. Справедлива формула
T(2k ) = 2k k −2k +1	(3)

Доказательство. При k=1 имеем T(21)=1 и начальные условия выполнены.

Пусть для k формула (3) есть решение соотношения (2). Тогда при k +1 имеем

T(2k+1 ) = 2T(2k ) +2k+1 −1 = 2(2k k −2k +1) +2k+1 −1 = = 2k+1 k −2k+1 +2k+1 +1 = (k +1)2k+1 −2k+1 +1.

Значит при k +1 формула (3) есть решение соотношения (2). Утверждение

доказано.
Ясно, что для произвольного n справедливо
Т(n)=O(n log n)	(4)

Таким образом, представленный рекурсивный алгоритм лучше по порядку исходного "наивного" алгоритма. Можно доказать, что данный алгоритм асимптотически оптимален.

2. Умножение n - разрядных двоичных чисел.

Даны два n - разрядных двоичных числа и требуется найти их произведение. "Наивный" алгоритм умножения "столбиком" требует O(n2 ) битовых операций. Предложим рекурсивный алгоритм для данной задачи. Пусть

x и у - два n - битовых числа и пусть n=2k , в противном случае дополняем числа слева нулями. Разобьем числа x и y на две равные части в виде x = a b ,

y = c d

и будем рассматривать каждую часть как 2n - разрядное двоичное число.

Тогда произведение x y можно представить в виде

	n			n			n
						+ d) = ac2n + (ad + bc)2
x y = (a 22			+ b)(c 22				2		+ bd (5)

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

(умножений на степень числа 2). Действительно, находим

u = (a + b)(c + d)
v = a c
w = b d	(6)

n

z = v 2n + (u − v − w)22 + w

Ясно, что операции сложения и сдвига имеют сложность O(n).

Заметим, что a+b и c+d имеют, вообще говоря, 2n +1 разрядов. Тогда запишем

109

				n
a + b = a		22 + b
	1						1
				n
c + d = c		22 + d
	1						1
									n
и (a + b)(c + d) = a c 2n
		+ (a d					+ b c )22				+ b d .
1	1	1				1	1	1			1	1

Произведение b1d1 находится с помощью рекурсивного алгоритма на задачах размера 2n . Остальные вычисления можно выполнить за время O(n), поскольку

они содержат один из аргументов либо единственный бит a1 или c1 , либо степень

числа 2.

Таким образом число используемых операций Т(n) ограничено сверху

			k	, при n = 1
	n				(7)
Т(n)=				+ kn, при n >1
	3T
		2

где k - постоянная, отражающая число сложений и сдвигов в алгоритме (6).

Утверждение 2. Справедлива формула
T(n) = 3knlog2 3 −2kn	(8)

Доказательство. При n=1 начальные условия выполнены. Пусть для n формула (8) есть решение соотношения (7). Тогда имеем

T(2n) = 3T(n) +2kn = 3[3knlog2 3 −2kn]+2kn = 3k(2n)log2 3 −2k(2n)

(Здесь использовано равенство 3 = 2log2 3 ). Таким образом, формула (8) справедлива для 2n. Утверждение доказано.

Ясно, что Т(n)=O(nlog2 3 ) и данный алгоритм лучше по порядку исходного

"наивного" алгоритма.

Для данной задачи известны и более лучшие алгоритмы, с которыми можно ознакомиться, например, в [2].

2a. Возведение в степень. Фиксируется элемент a

некоторой алгебраической системы с операцией умножения и натуральное число

n. Требуется найти an. Тривиальный алгоритм требует n - 1 умножение. Следующий рекурсивный алгоритм требует существенно меньшее число умножений. Алгоритм работает так:

Пусть u(n)= an. Если n=1, то u(1)=a. Если n >1, то находим k= 2n и l=res(2,n) - остаток от деления n на 2. Тогда справедливо

110

n					n
u(n) = u				u			, если l = 0
	2					2
	n					n
u(n) = u					u					a, если	l = 1
	2							2

Нетрудно убедиться, что в данном алгоритме используется не более 2[log2 n] умножений.

3. Умножение матриц. Даны две (n x n) матрицы с элементами из некоторого кольца K и требуется найти их произведение. Стандартный алгоритм

требует n3 умножений и n3 − n2 сложений элементов K . На первый взгляд кажется, что невозможно сколько-нибудь существенно снизить данное число операций. Однако, был предложен следующий алгоритм (Штрассен В., 1969):

Пусть n=1. Тогда произведение матриц находится одним умножением. Пусть n=2 и даны матрицы

a11	a12		b11	b12
A =			B =
a21	a22		b21	b22

и пусть	c	c
	A B = C = 11	12	.
	c21	c22
Тогда матрица C может быть вычислена так:
Пусть	p1=(a11 + a22 )(b11 + b22 )
	p2 =(a21 + a22 )b11
	p3 = a11 (b12 − b22 )
	p4 = a22 (−b11 + b21 )		(7)
	p5 =(a11 + a12 )b22

p6 =(−a11 + a21 )(b11 + b12 ) p7 =(a12 − a22 )(b21 + b22 )

Тогда находим

c11 = p1 + p4 − p5 + p7 c12 = p3 + p5

c21 = p2 + p4

c22 = p1 + p3 − p2 + p6

Заметим, в данном алгоритме использовано 7 умножений и 18 сложений и не использована коммутативность умножения.

Пусть теперь n = 2k+1. Тогда алгоритм умножения матриц работает так: матрицы A и B порядка 2k+1 ×2k+1 представляются как (2 x 2)-матрицы над кольцом матриц порядка 2k ×2k и применяется изложенный выше алгоритм умножения (2 x 2)-матриц. Если n ≠ 2k+1, то находится такое k, что

111

2k < n ≤ 2k+1, и к матрицам добавляется нужное число нулевых строк и столбцов.

Пусть Т(2k ) - число арифметических операций, используемых в алгоритме на матрицах размера 2k ×2k . Тогда справедливо соотношение

	T(2k+1 ) = 7T(2k ) +18(2k )2	(9)
	T(20 ) = 1
	Утверждение 3. Справедлива формула
	T(2k ) = 7k+1 −6 22k	(10)

Доказательство. При k=0,1, формула (10) справедлива. Пусть для k формула (10) есть решение соотношения (9). Имеем при k+1:

T(2k+1) = 7T(2k ) +18(2k )2 = 7(7k+1 −6 22k ) +18 22k =

= 7k+2 −42 22k +18 22k = 7k+2 −6 22(k+1) ,

т.е. формула (10) справедлива и для k+1. Утверждение доказано. Ясно, что выполняется

T(n) = O(7log2 n ) = O((2log2 7 )log2 n ) = O(nlog2 7 ) (11)

Значит, представленный алгоритм лучше по порядку исходного алгоритма (заметим что log2 7 = 2.807).

Для умножения (2x2)-матриц Виноград предложил алгоритм, требующий 7 умножений и 15 сложений:

s1 = a21 + a22	m1 = s2s6
s2 = s1 − a11	m2 = a11b11
s3 = a11 − a21	m3 = a12 b21
s4 = a12 − s2	m4 = s3s7
s5 = b12 − b11	m5 = s1s5
s6 = b22 − s5	m6 = s4 b22
s7 = b22 − b12	m7 = a22s8
s8 = s6 − b21
t1 = m1 + m2	t2 = t1 + m4
c11 = m2 + m3	c21 = t2 − m7
c12 = t1 + m5 + m6	c22 = t2 + m5

Использование данного алгоритма в качестве базового и рекурсии дает следующее рекуррентное уравнение для сложности соответствующего алгоритма.

T(2k+1 ) = 7T(2k ) +15 22k

T(20 ) = 1

Легко убедиться, что решением данного уравнения является

T(2k ) = 6 7k −5 22k .

112

Обратимся теперь к задаче обращения матриц. Для применимости предлагаемого алгоритма требуется предположить не только обратимость матрицы, но и обратимость матриц, появляющихся на промежуточных этапах алгоритма. (Аналогичные предложения имеются и в алгоритме Гаусса).

Рекурсивный алгоритм обращения матрицы следует из приводимых ниже легко проверяемых тождеств и трактовки (n x n)-матриц как (2x2)-матриц над

n				n
кольцом			x		-матриц.
	2
				2

A11

A12

E

0 A11

0

E A−1A

A =

A22

=

11

12

A21

A21A11−1

E

0

D

0

E

A−1

E

−A−1A

A−1

0

E

0

D = A

− A A−1A

=

11 12

11

,

0

E

0

D

−1

−A A−1

E

22

21 11 12

21

11

Для нахождения обратной (n x n)-матрицы используется 2 обращения, 6

n

n

умножений и 2 сложения

x

-матриц. Отсюда легко получить (используя

2

2

"быстрый" алгоритм умножения матриц), что сложность I(n) обращения матриц удовлетворяет соотношению

I(n) = O(nlog2 7 ) .

Далее, пусть T(n) - сложность умножения (n x n)-матриц и пусть T(2n) ≥ (2+ε)T(n) для некоторого ε>0 и всех n. Тогда из приведенного алгоритма обращения матрицы следует, что I(n)=O(T(n)). Заметим, что произведение (n x n)- матриц можно найти, обращая (3n x 3n)-матрицы, что следует из тождества

E

A

0

−1

E

−A

AB

0

E B

=

0 E

−B

0

0

0

E

0

E

Отсюда имеем I(3n) ≥ T(n) . Поскольку выполнено

T

n

≥ kT(n) для

4

некоторого k>0, то имеем I(n) ≥ k T(n) . Наконец, отправляясь от тождества

det A = det A11 det(A22 − A21A11−1A12 )

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

2°. Рассмотрим теперь в общем виде вопрос о сложности алгоритмов, использующих рекурсию. Из приведенных выше примеров, ясно, что сложность рекурсивных алгоритмов выражается рекуррентными соотношениями. Если в рекурсивном алгоритме используется одна процедура, то значение сложности

113

T(N) для задачи размера N определяется значениями Т(m) для аргументов m, где m <N . Однако возникающие при этой рекуррентные соотношения решаются в конечном виде в очень редких случаях. При равномерном разбиении задача

размера N разбивается на k подзадач размера Nk , k - некоторая фиксированная

константа в рекурсивном алгоритме, при этом функция сложности T(N) определяется рекуррентным соотношением вида:

	N
T(N) = A(N)T			+ B(N)	(12)
	k

T(1) = c

где c - константа, A(N),B(N) неотрицательные, целочисленные, монотонные функции, характеризующие сложность получения решения исходной задачи

размера N из k решений подзадач размера Nk . Ясно, что соотношение (12)

определяет однозначно функцию Т(N) только при значениях аргументов N вида

kp, Р=0,1,... . Для практических приложений представляет интерес выделение случаев, когда решение Т(N) соотношения (12) ограничено сверху полиномом от

N.

Легко доказывается следующее

Утверждение 4. Пусть функция А(N) удовлетворяет условию: существует

ε > 0, такое, что справедливо соотношение

A(kN) ≥ (1+ε)A(N) (13)

для всех натуральных N.

Тогда решение T(N) соотношения (12) не мажорируется сверху никаким полиномом от N.

Таким образом в дальнейшем ограничимся случаем A(N)=a, B(N)= bN t , где a,b,t - фиксированные целые числа.

Справедливо Утверждение 5. Пусть дано рекуррентное соотношение

	N			t
T(N) = aT			+ bN	(14)
	k
T(1) = c

где a,b,c,k,t - фиксированные константы. Тогда при N= kp, p=0,1, ... решением соотношения (14) является выражение

ap c + b ap p, если a = kt

p

a

T(k

p

−1

(15)

) =

p

c + b k

pt kt

, если a ≠ k

t

a

a

−1

k

t

114

Доказательство. Докажем утверждение индукцией по р. При р=0 имеем Т( k0 )=с в обоих случаях, и выражение (15) совпадает с начальными условиями. Пусть a= kt и при N= kp формула (15) является решением соотношения (14). Покажем справедливость этого при N1 = kp+1. Имеем

T(N ) = aT(kp) + bk(p+1)t

=

1

= a[ap c + b ap p]+ b k(p+1)t = a[ap c + b ap p]+ b ap+1 =

= ap+1 c + b ap+1 (p+1,)

т.е. при N

= kp+1

1

формула (15) является решением (14).

Пусть теперь a≠kt и при N= kp формула (15) есть решение (14). Тогда

имеем для N

= kp+1

1

a

p

−1

p

(p+1)t

p

pt kt

(p+1)t

T(N ) = aT(k

) + b k

= a a

c + b k

+ b k

=

1

a

−1

kt

a p

− a

a p+1

a

−1

= a

(p+1)

c + b k

(p+1)t

kt

(p+1)

(p+1)t kt

+1

= a

c + b k

a

a

kt

−1

−1

kt

k

t

и, значит, формула (15) является решением (14) при N = kp+1						, что и доказывает
утверждение.				1
Следствие. В предположениях предыдущего утверждения справедливы
соотношения
		t	logk N), если a = k		t
	O(N
T(N) =	O(N t )			, если a < kt (16)
				, если a > kt
	O(N logk a )

В некоторых случаях рекурсию для задачи размера N удается организовать только путем аддитивного уменьшения исходного размера задачи N на некоторую константу k . Сложность Т(N) такого типа рекурсивных алгоритмов определяется рекуррентным соотношением вида

T(N) = aT(N − k) + bN t (17)

T(0) = c

115

где a,b,c,t - константы. Например, такая ситуация возникает при решении графических задач.

Справедливо

Утверждение 6. Для функции Т(N), являющейся решением уравнения (17) при N=kр, p=0,1, ... справедлива оценка

N

N

c + bN

t a k

−1

a ≠ 1

a k

,

−1

T(N) ≤

a

(18)

c + b

N

t+1

, a = 1

k

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

N подзадач размера N . Для сложности T(N) рекурсивного алгоритма возникает следующее рекуррентное уравнение

T(N) = a NT( N ) + bN

(19)

T(2) = c

где a,b,c - фиксированные константы.

Данное соотношение определяет однозначно функцию T(N) при N=22n , n=0,1, ... .

Утверждение 7. Решением рекуррентного соотношения является выражение

	2n		2n −1			, a = 1
	n 2	b + c 2
						(20)
T(N) =				a	n
an c		22n −1	+ b			−1	, a ≠ 1
				a −1

Доказательство. Докажем утверждение индукцией по n . При n=0 имеем

T(220 ) = 1 в обоих случаях и выражение (20) совпадает с начальными условиями.

Пусть a=1 и при n формула (20) дает решение соотношения (19). Имеем при n +1

2n+1	2n	2n	2n+1	2n		2n	2n −1		2n+1	=
T(2	) = 2	T(2	) + b 2	= 2	n 2		b + c 2		+ b 2

= n 22n+1 b + c 22n+1 −1 + b 22n+1 = (n +1) 22n+1 b + c 22n+1 −1

и для n +1 формула (20) является решением соотношения (19). Пусть а ≠1 и при n утверждение справедливо. Имеем

116

2n+1

2n

2n

2n+1

2n

n

2n −1

an −1

2n

2n+1

T(2

) = a 2

T(2

) + b

2

= a 2

a

c 2

+ b

2

+ b 2

=

a −1

n+1

2n+1

−1

an −1

2n+1

2n+1

= a

c 2

+ ab

2

+ b 2

=

a −1

n+1

2n+1

−1

an −1

2n+1

n+1

2n+1

−1

an+1

−1

2n+1

= a

c 2

+ ab

+ b 2

= a

c 2

+ b

2

a −1

a −1

и при n +1 утверждение справедливо.

3°. Данные результаты имеют практический интерес. В качестве примера заметим, что для задачи сортировки можно предложить рекурсивные алгоритмы, использующие как разбиение задачи на произвольное фиксированное число подзадач так и квадратичное разбиение. Эти алгоритмы дают более лучшие оценки, чем приведенные выше.

Для задачи умножения матриц использование базового алгоритма умножения (r x r) -матриц с a умножениями для построения рекурсивного алгоритма, сводящего умножение (N x N) -матриц к умножению (N/r)x(N/r) -мат- риц приводит к оценкам для сложности T(N) :

	O(N logr a )			,если a > r2
T(N) =				,если a = r2
	O(N2 log	r	N)
	O(N2)			,если a < r2

(В алгоритме Штрассена r = 2, a = 7) В.Пан (1978) использовал алгоритм с параметрами r = 70 с a = 143640 и получил

T(N) = O(N2.796 )

В настоящее время известны и более лучшие алгоритмы.

Усилиями ряда математиков (Пан, Виноград, Романи, Шеихаге, Штрассен, Копперсмит) экспонента сложности матричного умножения последовательно принимала значения:

ω= 2.6054

ω=2.523

ω=2.5166

ω=2.495364

ω=2.40364

ω=2.376

Основная проблема - нахождение доказательства равенства ω = 2 еще не решена (1991).

Укажем на другие имеющиеся результаты по нахождению эффективных базовых алгоритмов умножения (r x r) - матриц.

117

Для r = 3 предложен алгоритм, использующий 23 умножения, но он не приводит к улучшению оценки, т.к. log3 21 < log2 7 < log3 22.

Для r = 5 найден алгоритм, использующий 100 умножений. Рассмотрим еще один пример применения полученных результатов.

Вернемся к задаче умножения чисел в двоичной записи. Зафиксируем натуральное число r ≥ 2 и рассмотрим два r n -битовых числа u и v, где

u= ur n−1... u1u0

v= vr n−1... v1v0

Разобьем эти числа на r частей

u= ur−12(r−1)n +...+u12n + u0

v= vr−12(r−1)n +...+v12n + v0

Здесь каждое ui и vi являются n - битовыми числами, i 1,r −1.

Рассмотрим многочлены

u(x) = ur−1xr−1 +...+u1x + u0

v(x) = vr−1xr−1 +...+v1x + v0

и образуем произведение

w(x) = u(x) v(x) = w2(r−1) x2(r−1) +...+w1x + w0

Ясно, что выполнено

u = u(2n ) v = v(2n )

u v = w(2n )

Поэтому, знание многочлена w(x) позволяет вычислить произведение u v за число действий, пропорциональное n . Чтобы найти коэффициенты многочлена w(x) находим значение w(x) в 2(r -1) точках 0,1, ... ,2(r -1):

u(0)v(0)=w(0), u(1)v(1)=w(1),... , u(2(r -1)) v(2(r -1)) =w(2(r -1)).

Разрядность чисел u(i) (соответственно v(i) ) не превышает n + t, где t - некоторая константа, зависящая от r. Ясно, что если Т(n) - сложность умножения n - битовых чисел, то сложность умножения (n + t) - битовых чисел есть T(n)+c’n для некоторой константы с’.

Если Т(r n) - сложность умножения r n - битовых чисел, то справедливо

соотношение

T(r n) = (2(r −1) +1)T(n) + c′′n

( c′′ - константа).

Отсюда, согласно (16), получаем

T(n) = O(nlogr (2(r−1)+1) )

Поскольку имеем logr (2(r −1) +1) <1+ logr 2 и, обозначая ε = logr 2 можно

записать

T(n) = O(n1+ε )

118

Таким образом, доказано

Утверждение 8. Дня любого ε >0 существует алгоритм умножения n - битовых чисел, для которого сложность удовлетворяет соотношению

T(n) = O(n1+ε )

Имеются и более эффективные алгоритмы умножения чисел, но они используют уже не цифровые операции.

119

§18. Алгоритм быстрого преобразования Фурье

иего приложения.

1° Преобразование Фурье имеет многочисленные применения в математике и кибернетике. Задача дискретного преобразования Фурье возникает в обработке сигналов. Алгоритм дискретного преобразования Фурье используется как подпрограмма в различных арифметических и алгебраических задачах, включая вычисление и интерполяцию полиномов и умножение чисел и полиномов. Дискретное преобразование Фурье можно рассматривать как переход от представления полинома его коэффициентами к представлению его значениями в специально выбранных точках. Этими точками являются корни из единицы, и быстрое преобразование Фурье (БПФ) есть эффективный метод выполнения этого преобразования, а также ему обратного.

В данном разделе дается алгоритм БПФ и приводится верхняя оценка сложности его реализации. В качестве приложения рассматривается проблема умножения двух полиномов n -ой степени, для которой БПФ требует O(n log n)

арифметических операций, в то время как обычный алгоритм требует O( n2 ) операций. Шенхаге и Штрассен (1971) применили БПФ для построения алгоритма умножения двух n -битовых чисел, который требует O(n log n log log n) операций.

2° Для дискретного преобразования Фурье будем называть прямым преобразованием переход от представления полинома степени n коэффициентами

к представлению его значениями в точках, т.е.

< a0,..., an > → << x0, y0 >,..., < xs, ys >>,

где s ≥ n+1, n - степень полинома. Соответственно обратным преобразованием - переход от представления значениями в точках к представлению коэффициентами.

Утверждение 1. Пусть имеется алгоритм со сложностью O(n log n) для выполнения прямого и обратного преобразования Фурье. Тогда имеется алгоритм той же сложности для умножения двух полиномов n -ой степени.

Доказательство. Пусть требуется перемножить полиномы p(x)= ∑nj=0 aj x j

и q(x)= ∑nj=0 bj x j . Умножение осуществляем следующим образом:

Шаг 1.	Осуществляем прямое преобразование Фурье и
вычисляем p(x)					x=x ;		0 ≤ i ≤ 2n
					i
					n = deg p = deg q .
	q(x)	x=x ,
			i
Шаг 2.	Вычисляем w(xi ) = p(xi )q(xi ), 0 ≤ i ≤ 2n.
Шаг 3.	Осуществляем обратное преобразование Фурье и
по парам < x				, w(x		) > , 0 ≤ i ≤ 2n находим полином,
	{		i		i		}

т.е. его коэффициенты, степени ≤ 2n, который в данных точках принимает данные значения.

120

Определим сложность данного алгоритма. По предположению сложность шага 1 есть O(n log n), шага 2 - 2n+1, шага 3 - O(n log n) и общее число операций, следовательно, равно O(n log n). Утверждение доказано.

Заметим, что обычный алгоритм требует O( n2 ) операций.

Задача теперь заключается в том, чтобы выбрать точки {xi }, в которых

возможно быстрое преобразование Фурье.

Будем предполагать, что операции выполняются в поле комплексных чисел

С.

Напомним, что число ω называется примитивным корнем степени k из единицы, если

ωk = 1 и ω j ≠ 1 при j [1,k −1].

Множество корней степени k из 1 образует группу по умножению и примитивные корни это образующие данной группы.

Утверждение 2. Пусть ω - примитивный корень степени n +1 из 1. Тогда выполнено:

n n +1, если α ≡ 0(mod(n +1))

∑s=0ωsα = 0, если сравнение неверно.

Доказательство. Если α ≡ 0(mod(n +1)),то ωsα = 1 по определению.

Если сравнение неверно, то ∑n

ωsα =

∑n

ts

t=ω

α =

tn+1 −1

α = 0, т.к.

t = ωα ≠ 1 и

s=0

s=0

t -1

t=ω

tn+1 = ωα(n+1) = 1. Утверждение доказано.

Утверждение 3. Выберем точки xi

= ωi, 0 ≤ i ≤ n, где ω - примитивный

корень степени n +1 из 1. Тогда прямое и обратное преобразования полинома

степени n требует O(n log n) операций.

Доказательство. Используем данные точки x0,..., xn для преобразования

Фурье. Пусть дан многочлен p(x)= ∑nj=0 aj x j

и выполним прямое преобразование

p(x)= ∑nj=0aj x j

x=xj следующим образом:

Считаем, что n +1=2r . Имеем p(x) = a

+ a x+...+a

n

xn =

0

1

=(a0 + a2x2 +...+an−1xn−1 ) + (a1x + a3 x3 +...+anxn ) =

=(a0 + a2x2 +...+an−1xn−1 ) + x(a1 + a3x2 +...+anxn−1 ) .

Положим y = x2 . Тогда имеем

n−1 n−1

p(x) = (a0 + a2 y+...+an−1 y 2 ) + x(a1 + a3 y+...+an y 2 ) = p1 (y) + xp2 (y) ,

где deg p1 = deg p2 = n 2−1 = 2r−1 −1.

121

T(2r ) = 2T(2r−1 ) + 32 2r, T(1) = 0. Отсюда получаем

Вычисление p(x) в точках x0,..., xn сводится к p1 (y) и p2 (y) в точках

y ,..., y , где y			= x2, среди которых		n +1	различных.
0	n	i	i	2
	Данный процесс организуем рекурсивно, решая 2 задачи половинной
размерности.
	Оценим сложность Т(2r ) - число арифметических операций для
вычисления многочлена ∑2i=r				0−1 ai xi в выбранных 2r точках {ωt				0 ≤ t ≤ 2r -1},

где ω - примитивный корень степени 2r из 1. Тогда имеем

T(2r ) = 2T(2r−1 ) +2 2r,

где последний член представляет одно сложение и одно умножение для каждого xi .

Теперь заметим, что можно уменьшить число умножений в два раза, используя соотношение xi+2r−1 = −xi .

Значит можно записать

r

3

r

T(2 )

=

2 r . Значит T(n)=O(n log n).

2

Найдем обратное преобразование: {< xi , yi

>}→ {ai }, где xi = ωi , где ω -

примитивный корень степени n +1 из 1.

Организуем вычисление как умножение вектора на матрицу. Положим

1

1

1

... 1

ω

ω2

... ωn

1

ω2

ω4

V = 1

... ω2n

. . .

n2

ω

n

ω

2n

... ω

1

(

0

n )

(

0

n )

( 0

n )

(

0

n )

Тогда

a ,..., a

V

=

y ,..., y

и

a ,..., a

=

y ,..., y

V −1.

~

~

~

ω

−ij

Определим (n +1× n +1)-матрицу V =

(vij ) , где

vij =

. Имеем согласно

1, если i = j,

n +1

(

~

утверждению 2

)

=

V V

ij

0, если i ≠ j.

~

и поэтому V

−1

= V.

n )

(

0

n )

Следовательно,

(

0

=

a ,..., a

y ,..., y

V −1 =

122

	1	1	... 1
		ω-1	... ω-n
	1				1				1
= (y0	,..., yn )						= ∑in=0 yiti	t=ω− j			,	(0 ≤ j ≤ n).
		. . .			n +1				n +
										1
		ω-n	2
	1		... ω-n

Если ω - примитивный корень степени n +1 из 1, то это верно и для ω−1 , поэтому обратное преобразование Фурье эквивалентно прямому преобразованию и, следовательно требует O(n log n) арифметических операций.

Если n - не степень двойки, то заменяем ее ближайшей сверху степенью двойки. Ясно, что это сохраняет порядок оценки.

Следствие. Умножение двух многочленов степени n можно выполнить за O(n log n) операций в поле комплексных чисел.

Заметим, что имеются алгоритмы БПФ с операциями в конечных полях. Для знакомства с ними следует обратиться к журнальной литературе.

123