В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 21

При равномерном разбиении задачаразмера N разбивается на k подзадач размераN, k - некоторая фиксированнаяkконстанта в рекурсивном алгоритме, при этом функция сложности T(N)определяется рекуррентным соотношением вида: NT( N ) = A( N ) T  + B( N ) k(12)T(1) = cгде c - константа, A(N),B(N) неотрицательные, целочисленные, монотонныефункции, характеризующие сложность получения решения исходной задачиразмера N из k решений подзадач размераN. Ясно, что соотношение (12)kопределяет однозначно функцию Т(N) только при значениях аргументов N видаk p , Р=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( N ) = aT  + bN t k(14)T(1) = cгде a,b,c,k,t - фиксированные константы. Тогда при N= k p , p=0,1, ... решениемсоотношения (14) является выражениеa p ⋅ c + b ⋅ a p ⋅ p, если a = k tpa t  −1T( k p ) = ppt  k , если a ≠ k ta ⋅ c + b ⋅ ka−1tk(15)114Доказательство. Докажем утверждение индукцией по р. При р=0 имеемТ( k 0 )=с в обоих случаях, и выражение (15) совпадает с начальными условиями.Пусть a= k t и при N= k p формула (15) является решением соотношения (14).Покажем справедливость этого при N1 = k p+1 . ИмеемT( N1 ) = aT( k p ) + bk ( p+1)t =[][]= a a p ⋅ c + b ⋅ a p ⋅ p + b ⋅ k ( p+1)t = a a p ⋅ c + b ⋅ a p ⋅ p + b ⋅ a p+1 == a p+1 ⋅ c + b ⋅ a p+1 ( p +1), т.е.

при N1 = k p+1формула (15) является решением (14).Пусть теперь a≠ k t и при N= k p формула (15) есть решение (14). Тогдаимеем для N1 = k p+1T( N1 ) = aT( k p ) + b ⋅ k ( p+1)t= a a p ⋅ c + b ⋅ k ptp a t  − 1k  + b ⋅ k ( p+1)t =a1−ktp+1  a p a−1 a t  − a t= a( p+1) ⋅ c + b ⋅ k ( p+1)t  k+ 1 = a( p+1) ⋅ c + b ⋅ k ( p+1)t k t  a   a k   t  − 1 t  −1k kи, значит, формула (15) является решением (14) при N1 = k p+1 , что и доказываетутверждение.Следствие.

В предположениях предыдущего утверждения справедливысоотношенияO( N t log k N ), если a = k tT( N ) = O( N t ), если a < k tlog k a) , если a > k tO( N(16)В некоторых случаях рекурсию для задачи размера N удается организоватьтолько путем аддитивного уменьшения исходного размера задачи N на некоторуюконстанту k . Сложность Т(N) такого типа рекурсивных алгоритмов определяетсярекуррентным соотношением видаT( N ) = aT( N − k) + bN tT(0) = c(17)115где a,b,c,t - константы.

Например, такая ситуация возникает при решенииграфических задач.СправедливоУтверждение 6. Для функции Т(N), являющейся решением уравнения (17)при N=kр, p=0,1, ... справедлива оценкаN Nk −1 kt a, a≠1a ⋅ c + bNa −1T( N ) ≤ N t+1c+ b, a=1k(18)В некоторых случаях для организации рекурсии используется"квадратичное" разбиение, при котором исходная задача размера N разбивается наN подзадач размера N . Для сложности T(N) рекурсивного алгоритмавозникает следующее рекуррентное уравнениеT( N ) = a N T( N ) + bNT(2) = c(19)где a,b,c - фиксированные константы.nДанное соотношение определяет однозначно функцию T(N) при N= 22 ,n=0,1, ...

.Утверждение 7. Решением рекуррентного соотношения являетсявыражениеn ⋅ 22n ⋅ b + c ⋅ 22n −1 , a = 1T( N ) = an − 12n −1n, a≠1+ba ⋅ c ⋅ 2a −1(20)Доказательство. Докажем утверждение индукцией по n . При n=0 имеем0T(22 ) = 1 в обоих случаях и выражение (20) совпадает с начальными условиями.Пусть a=1 и при n формула (20) дает решение соотношения (19).Имеем при n +1n +1nn+1nT(22 ) = 22 ⋅ T(22 ) + b ⋅ 22n +1= n ⋅ 22n +1⋅ b + c ⋅ 22−1nnnn +1= 22  n ⋅ 22 ⋅ b + c ⋅ 22 −1  + b ⋅ 22 =n +1+ b ⋅ 22n +1= ( n + 1) ⋅ 22n +1⋅ b + c ⋅ 22−1и для n +1 формула (20) является решением соотношения (19).Пусть а ≠1 и при n утверждение справедливо. Имеем1162n+1T(22n2n2n+1) = a ⋅ 2 T(2 ) + b ⋅ 2 nn +1a n − 1 2n 2n −12  + b ⋅ 22 == a ⋅ 2 a c ⋅ 2+ba −12nn +1a n − 1 2n+12= a c⋅2+ ab+ b ⋅ 22 =a −1a n − 1  2n+1a n+1 − 1 2n+12n+1 −1 2n+1 −1n+1n+12= a c⋅2+  ab+ b2= a c ⋅2+ba1a1−−n+12n+1 −1и при n +1 утверждение справедливо.3°.

Данные результаты имеют практический интерес. В качестве примеразаметим, что для задачи сортировки можно предложить рекурсивные алгоритмы,использующие как разбиение задачи на произвольное фиксированное числоподзадач так и квадратичное разбиение. Эти алгоритмы дают более лучшиеоценки, чем приведенные выше.Для задачи умножения матриц использование базового алгоритмаумножения (r x r) -матриц с a умножениями для построения рекурсивногоалгоритма, сводящего умножение (N x N) -матриц к умножению (N/r)x(N/r) -матриц приводит к оценкам для сложности T(N) :O( N log r a ),если a > r 2T( N ) = O( N 2 log r N ) ,если a = r 22,если a < r 2O( N )(В алгоритме Штрассена r = 2, a = 7) В.Пан (1978) использовал алгоритм спараметрами r = 70 с a = 143640 и получилT( N ) = O( N 2.796 )В настоящее время известны и более лучшие алгоритмы.Усилиями ряда математиков (Пан, Виноград, Романи, Шеихаге, Штрассен,Копперсмит) экспонента сложности матричного умножения последовательнопринимала значения:ωωωωωω= 2.6054= 2.523= 2.5166= 2.495364= 2.40364= 2.376Основная проблема - нахождение доказательства равенства ω = 2 еще нерешена (1991).Укажем на другие имеющиеся результаты по нахождению эффективныхбазовых алгоритмов умножения (r x r) - матриц.117Для r = 3 предложен алгоритм, использующий 23 умножения, но он неприводит к улучшению оценки, т.к.

log 3 21 < log 2 7 < log 3 22.Для r = 5 найден алгоритм, использующий 100 умножений.Рассмотрим еще один пример применения полученных результатов.Вернемся к задаче умножения чисел в двоичной записи. Зафиксируемнатуральное число r ≥ 2 и рассмотрим два r⋅ n -битовых числа u и v, гдеu = ur⋅n−1... u1u0v = vr⋅n−1... v1v0Разобьем эти числа на r частейu = ur −12( r −1) n +...+ u12n + u0v = vr −12( r −1) n +...+ v12n + v0Здесь каждое ui и vi являются n - битовыми числами, i ∈1,r − 1 .Рассмотрим многочленыu( x) = ur −1x r −1 +...+ u1x + u0и образуем произведениеv( x) = vr −1 x r −1 +...+ v1x + v0w( 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( n log r (2( r −1) +1) )Поскольку имеем log r (2( r − 1) + 1) < 1 + log r 2 и, обозначая ε = log r 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 logn) операций.2°Для дискретного преобразования Фурье будем называть прямымпреобразованием переход от представления полинома степени n коэффициентамик представлению его значениями в точках, т.е.< a0 ,..., an > → << x0 , y0 >,..., < xs , ys >> ,где s ≥ n+1, n - степень полинома.

Соответственно обратным преобразованием переход от представления значениями в точках к представлениюкоэффициентами.Утверждение 1. Пусть имеется алгоритм со сложностью O(n log n) длявыполнения прямого и обратного преобразования Фурье. Тогда имеется алгоритмтой же сложности для умножения двух полиномов n -ой степени.nДоказательство. Пусть требуется перемножить полиномы p(x)= ∑ j =0 a j x jи q(x)=n∑ j =0 bj x j . Умножение осуществляем следующим образом:Шаг 1. Осуществляем прямое преобразование Фурье ивычисляем p( x)q( x)x = xi ,x = xi ;0 ≤ i ≤ 2nn = deg p = deg q .Шаг 2. Вычисляем w( xi ) = p( xi ) q( xi ), 0 ≤ i ≤ 2n .Шаг 3. Осуществляем обратное преобразование Фурье ипо парам {< xi , w( xi ) >}, 0 ≤ i ≤ 2n находим полином,т.е.

его коэффициенты, степени ≤ 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.