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

Тогда последовательность дополняется нулями, так, чтобы еедлина стала степенью двойки.Пусть Т(n) - число попарных сравнений, используемых в данномалгоритме для произвольной последовательности длины n. Тогда получаемсоотношение n 2Т(n)= 2T  + n − 1(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 = ab ,y= cdи будем рассматривать каждую часть какn- разрядное двоичное число.2Тогда произведение x ⋅ y можно представить в видеx⋅ y =n( a ⋅ 22+nb)( c ⋅ 22nbc)22n(5)+ d ) = ac2 + ( ad ++ bdРавенство (5) дает способ вычисления произведения x ⋅ y с помощью четырехnумножений - разрядных чисел и некоторого числа сложений и сдвигов2(умножений на степень числа 2).Действительно, находимu = ( a + b)( c + d )v = a⋅ cw = b⋅ dz = v ⋅ 2n + ( u − v −(6)nw)22+wЯсно, что операции сложения и сдвига имеют сложность O(n).Заметим, что a+b и c+d имеют, вообще говоря,запишемn+1 разрядов.

Тогда2109a + b = a1n⋅ 22+ b1c + d = c1n⋅ 22+ d1n)22и ( a + b)( c + d ) = a1 c1 2n + ( a1 d1 + b1 c1+ b1 d1 .Произведение b1 d1 находится с помощью рекурсивного алгоритма на задачахn. Остальные вычисления можно выполнить за время O(n), поскольку2они содержат один из аргументов либо единственный бит a1 или c1 , либо степеньразмерачисла 2.Таким образом число используемых операций Т(n) ограничено сверхуk, при n = 1Т(n)=  n3T  + kn, при n > 1 2(7)где k - постоянная, отражающая число сложений и сдвигов в алгоритме (6).Утверждение 2.

Справедлива формулаT( n) = 3kn log2 3 − 2kn(8)Доказательство. При n=1 начальные условия выполнены. Пусть для nформула (8) есть решение соотношения (7). Тогда имеем[]T(2n) = 3T( n) + 2kn = 3 3kn log2 3 − 2kn + 2kn = 3k(2n) log2 3 − 2k(2n)log 3(Здесь использовано равенство 3 = 2 2 ). Таким образом, формула (8)справедлива для 2n. Утверждение доказано.log 3Ясно, что Т(n)= O( n 2 ) и данный алгоритм лучше по порядку исходного"наивного" алгоритма.Для данной задачи известны и более лучшие алгоритмы, с которыми можноознакомиться, например, в [2].2a. Возведение в степень. Фиксируется элемент aнекоторой алгебраической системы с операцией умножения и натуральное числоn.

Требуется найти a n . Тривиальный алгоритм требует n - 1 умножение.Следующий рекурсивный алгоритм требует существенно меньшее числоумножений. Алгоритм работает так: n Пусть u(n)= a n . Если n=1, то u(1)=a. Если n >1, то находим k=   и2l=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[ log 2 n] умножений.3. Умножение матриц.

Даны две (n x n) матрицы с элементами изнекоторого кольца K и требуется найти их произведение. Стандартный алгоритмтребует n3 умножений и n3 − n2 сложений элементов K . На первый взглядкажется, что невозможно сколько-нибудь существенно снизить данное числоопераций. Однако, был предложен следующий алгоритм (Штрассен В., 1969):Пусть n=1. Тогда произведение матриц находится одним умножением.Пусть n=2 и даны матрицыи пустьa aA =  11 12  a21 a22 c cA ⋅ B = C =  11 12  . c21 c22 bB =  11 b21b12 b22 Тогда матрица C может быть вычислена так:Пустьp1 = ( a11 + a22 )( b11 + b22 )p2 = ( a21 + a22 ) b11p3 = a11 ( b12 − b22 )p4 = a22 ( − b11 + b21 )(7)p5 = ( a11 + a12 ) b22p6 = (− a11 + a21 )( b11 + b12 )p7 = ( a12 − a22 )( b21 + b22 )Тогда находимc11 = p1 + p4 − p5 + p7c12 = p3 + p5c21 = p2 + p4c22 = 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, что1112k < n ≤ 2k +1 , и к матрицам добавляется нужное число нулевых строк истолбцов.Пусть Т( 2k ) - число арифметических операций, используемых в алгоритмена матрицах размера 2k × 2k .

Тогда справедливо соотношениеT(2k +1 ) = 7T(2k ) + 18(2k ) 20T(2 ) = 1(9)Утверждение 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( n log2 7 )(11)Значит, представленный алгоритм лучше по порядку исходного алгоритма(заметим что log 2 7 = 2.807 ).Для умножения (2x2)-матриц Виноград предложил алгоритм, требующий 7умножений и 15 сложений:s1 = a21 + a22m1 = s2 s6s2 = s1 − a11m2 = a11 b11s3 = a11 − a21m3 = a12 b21s4 = a12 − s2m4 = s3 s7s5 = b12 − b11m5 = s1 s5s6 = b22 − s5m6 = s4 b22s7 = b22 − b12m7 = a22 s8s8 = s6 − b21t1 = m1 + m2t2 = t1 + m4c11 = m2 + m3c21 = t2 − m7c12 = t1 + m5 + m6c22 = t2 + m5Использование данного алгоритма в качестве базового и рекурсии даетследующее рекуррентное уравнение для сложности соответствующего алгоритма.T(2k +1 ) = 7T(2k ) + 15 ⋅ 22kT(20 ) = 1Легко убедиться, что решением данного уравнения являетсяT(2k ) = 6 ⋅ 7k − 5 ⋅ 22k .112Обратимся теперь к задаче обращения матриц.

Для применимостипредлагаемого алгоритма требуется предположить не только обратимостьматрицы, но и обратимость матриц, появляющихся на промежуточных этапахалгоритма. (Аналогичные предложения имеются и в алгоритме Гаусса).Рекурсивный алгоритм обращения матрицы следует из приводимых нижелегко проверяемых тождеств и трактовки (n x n)-матриц как (2x2)-матриц над n n 2 2кольцом  x  -матриц.AA =  11 A21A−1A12   E =−1A22   A21 A11−1−1 E − A11A12   A11=0E  00   A11E  0E0 −1D −1   − A21 A110ED  0−1A11A12 E 0−1, D = A22 − A21 A11 A12EДля нахождения обратной (n x n)-матрицы используется 2 обращения, 6умножений и 2 сложения n n x  -матриц.

Отсюда легко получить (используя 2 2"быстрый" алгоритм умножения матриц), что сложность I(n) обращения матрицудовлетворяет соотношениюI( n) = O( n log2 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00A 0E B0 E−1 E − A AB=  0 E − BE0 0  n Отсюда имеем I(3n) ≥ T(n) . Поскольку выполнено T   ≥ kT( n) для  4некоторого k>0, то имеем I(n) ≥ k T(n) .Наконец, отправляясь от тождества−1det A = det A11 ⋅ det( A22 − A21 A11A12 )можно показать, что сложность вычисления определителя матриц с точностью доконстанты совпадает со сложностью обращения матрицы.

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