Может ли кто-нибудь сказать мне о сложности сложения и вычитания для алгоритма умножения матриц «разделяй и властвуй»?

Может ли кто-нибудь сказать мне о сложности сложения и вычитания для алгоритма умножения матриц «разделяй и властвуй»?

Я знаю, что сложность операций сложения и вычитания классического матричного умножения составляет (n ^ 3-n ^ 2), а у Штрассена — 6n ^ 2,81 — 6n ^ 2... но я не могу найти разделяй и властвуй в любом месте. Просто представьте, что если кто-то и узнает, так это вы, ребята. Спасибо


algorithm matrix matrix-multiplication complexity-theory
person user1189352    schedule 20.02.2012    source источник
comment
Стандартный подход «разделяй и властвуй» по-прежнему кубичен — рекуррентное отношение равно T(n) = 8T(n/2) + O(n^2), которое является кубическим по основной теореме. Я не знаю точных констант, хотя, извините.   -  person Stuart Golodetz    schedule 20.02.2012
comment
возможный дубликат Выполняет ли умножение матриц Divide & Conquer такое же количество сложений/вычитаний, что и умножение классической матрицы?   -  person ninjagecko    schedule 23.02.2012

Ответы (1)


arrow_upward
1
arrow_downward

Это может помочь. См. раздел введения перед методом Штрассена.

person Tejas Patil    schedule 20.02.2012