Алгоритм для избиения алгоритма Штрассена

Question

Профессор Цезарь хочет разработать алгоритм матричного умножения, который равен асимптотически быстрее алгоритма Штрассена. Его алгоритм будет использовать метод деления и покоя, делящий каждую матрицу на куски размером n/4 x n/4, а вместе с разделяющими и комбинированными шагами выберем время Theta (n^2).

Answer 1

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

Допустим, вы разделите ваши матрицы на блоки каждой размерности (п/к) Х (п/к) (в вашем вопросе, к является 4). Тогда каждая матрица будет иметь ^{к 2} блоков, и будет ^{к 3} блока умножений (каждый блок в первой матрице будет умножен на к блоков во второй матрице). Следовательно, сложность рецидивы

Т (п) = к Т (п/к) + Θ (п).

По case 1 of the Master theorem, это означает,

T (N) = Θ ^{(п журнал _к (K)}) = Θ (п).

Это то же самое, что и обычное умножение матрицы. Очевидно, это не превзойдет Штрассена.