Предположим, квадратные матрицы.
Если вы подсчитаете количество сложений (нет вычитаний) в классическом умножении матриц, вы получите N ^ 3 сложений. Есть N ^ 2 элементов, и каждый элемент является точечным произведением строки и столбца, состоящих из N-1 сложений, так что почти точно N ^ 3 сложений.
Чтобы подсчитать количество сложений в умножении матрицы «разделяй и властвуй», давайте посмотрим, как это работает:
Разделите матрицу NxN на четыре (N / 2) x (N / 2) матрицы, затем обработайте ее как матрицу 2x2 и выполните рекурсивное умножение блоков. Например, умножение двух матриц 8x8:
┌┌A A A A┐┌B B B B┐┐ ┌┌a a a a┐┌b b b b┐┐
││A A A A││B B B B││ ││a a a a││b b b b││
││A A A A││B B B B││ ││a a a a││b b b b││
│└A A A A┘└B B B B┘│ │└a a a a┘└b b b b┘│
│┌C C C C┐┌D D D D┐│*│┌c c c c┐┌d d d d┐│
││C C C C││D D D D││ ││c c c c││d d d d││
││C C C C││D D D D││ ││c c c c││d d d d││
└└C C C C┘└D D D D┘┘ └└c c c c┘└d d d d┘┘
Новая матрица будет:
┌┌ ┐┌ ┐┐
││ Aa+Bc ││ Ab+Bd ││
││ ││ ││
│└ ┘└ ┘│
│┌ ┐┌ ┐│
││ Ca+Dc ││ Cb+Dd ││
││ ││ ││
└└ ┘└ ┘┘
(where for example Aa is a 4x4 matrix multiplication)
Каждое умножение [N / 2xN / 2] * [N / 2xN / 2] является подзадачей размера N / 2. Мы должны сделать 8 из этих подзадач. Это дает нам повторение из вышесказанного:
additions[N] = 8*additions[N/2] + N^2
То есть, если мы заплатим цену за N ^ 2 дополнения, нам будет разрешено разбить проблему размера N на 8 подзадач размера N / 2.
Мы можем решить, используя основную теорему (или более общую теорему Акра-Бацци), или путем проверки:
additions[N] = 8*(8*(8*(8*(..1..) +(N/8)^2) +(N/4)^2) +(N/2)^2) +N^2
Использование основной теоремы , additions[N] = O(N^(log_2(8))) = O(N^3)
Зачем нам это делать, поскольку это тот же порядок роста? Мы бы не стали. Оказывается, чтобы улучшить асимптотическую сложность, вы не хотите этого делать, вы хотите использовать алгебраический прием, называемый методом Штрассена. См. http://www.cs.berkeley.edu/~jordan/courses/170-fall05/notes/dc.pdf на стр. 4. Наше новое отношение повторения основано на подсчете количества умножений и сложений, как показано на этой странице. Для формирования матрицы NxN требуется 18 добавлений матриц [N / 2xN / 2].
additions[N] = 7*additions[N/2] + 18*(N/2)^2
= 7*additions[N/2] + (18/4)*(N/2)^2
Как мы видим, нам нужно выполнить на одну подзадачу меньше, но за счет выполнения большей работы по объединению. Основная теорема гласит, что additions[N] = O(N^(log_2(7))) ~= O(N^2.807).
Так что асимптотически, будет МЕНЬШЕ дополнений, но только асимптотически. Реальная история раскрывается, когда мы моделируем оба рекуррентных отношения:
#!/usr/bin/python3
n = 1 # NxN matrix
normal = 1
naive = 1
strassen = 1
print('NUMBER OF ADDITIONS')
print(' NxN | normal naive strassen | best')
print('-'*60)
while n < 1000000000:
n *= 2
normal = (n-1)*n**2
naive = 8*naive + n**2
strassen = 7*strassen + (18/4)*n**2
print('{:>10} | {:>8.2e} {:>8.2e} {:>8.2e} | {}'.format(
n,
normal, naive, strassen/normal,
'strassen' if strassen<n**3 else 'normal'
))
Результаты:
NUMBER OF ADDITIONS
NxN | normal naive strassen | best
------------------------------------------------------------
2 | 4.00e+00 1.20e+01 2.50e+01 | normal
4 | 4.80e+01 1.12e+02 2.47e+02 | normal
8 | 4.48e+02 9.60e+02 2.02e+03 | normal
16 | 3.84e+03 7.94e+03 1.53e+04 | normal
32 | 3.17e+04 6.45e+04 1.12e+05 | normal
64 | 2.58e+05 5.20e+05 7.99e+05 | normal
128 | 2.08e+06 4.18e+06 5.67e+06 | normal
256 | 1.67e+07 3.35e+07 4.00e+07 | normal
512 | 1.34e+08 2.68e+08 2.81e+08 | normal
1024 | 1.07e+09 2.15e+09 1.97e+09 | normal
2048 | 8.59e+09 1.72e+10 1.38e+10 | normal
4096 | 6.87e+10 1.37e+11 9.68e+10 | normal
8192 | 5.50e+11 1.10e+12 6.78e+11 | normal
16384 | 4.40e+12 8.80e+12 4.75e+12 | normal
32768 | 3.52e+13 7.04e+13 3.32e+13 | strassen
65536 | 2.81e+14 5.63e+14 2.33e+14 | strassen
131072 | 2.25e+15 4.50e+15 1.63e+15 | strassen
262144 | 1.80e+16 3.60e+16 1.14e+16 | strassen
524288 | 1.44e+17 2.88e+17 7.98e+16 | strassen
1048576 | 1.15e+18 2.31e+18 5.59e+17 | strassen
2097152 | 9.22e+18 1.84e+19 3.91e+18 | strassen
4194304 | 7.38e+19 1.48e+20 2.74e+19 | strassen
8388608 | 5.90e+20 1.18e+21 1.92e+20 | strassen
16777216 | 4.72e+21 9.44e+21 1.34e+21 | strassen
33554432 | 3.78e+22 7.56e+22 9.39e+21 | strassen
67108864 | 3.02e+23 6.04e+23 6.57e+22 | strassen
134217728 | 2.42e+24 4.84e+24 4.60e+23 | strassen
268435456 | 1.93e+25 3.87e+25 3.22e+24 | strassen
536870912 | 1.55e+26 3.09e+26 2.25e+25 | strassen
1073741824 | 1.24e+27 2.48e+27 1.58e+26 | strassen
Как мы видим, только в отношении сложений Штрассен превосходит традиционное нормальное умножение матриц по количеству сложений , но только после того, как ваши матрицы превышают размер примерно 30000x30000.
(Также обратите внимание, что наивное умножение «разделяй и властвуй» выполняет асимптотически то же самое с точки зрения сложений, что и традиционное умножение матриц. Однако оно по-прежнему работает «хуже» вначале с коэффициентом 3, но по мере увеличения размера матрицы , асимптотически хуже с коэффициентом ровно 2. Конечно, это ничего не говорит нам об истинной сложности, которая включает в себя умножения, но если бы это произошло, мы все равно могли бы использовать его, если бы у нас был параллельный алгоритм, который мог бы использовать преимущества различных вычислений структура.) * * тысяча сорок четыре