擊敗Strassen算法的算法

-4

Caesar教授希望開發一種比Strassen算法漸近更快的矩陣乘法算法。他的算法將使用分而治之的方法，將每個矩陣分割成大小爲n/4 x n/4的棋子，並且分割和合並步驟將花費Theta（n^2）時間。擊敗Strassen算法的算法

您是否可以在試圖解決此問題時展示*任何*努力？ –

@ScottHunter我在網上發現了這個解決方案，但我不明白。 http://clrs.skanev.com/04/05/02.html – useruser1412

什麼解決方案？我沒有看到任何解決方案。 –

你並沒有真正指出問題在這裏，但我想這是反駁這個微不足道的算法運行速度比Strassen快。

說您將您的矩陣轉換成塊，每個維的（N/K）X（N/K）（在你的問題，ķ是4）。然後，每個矩陣將具有^ķ2塊，而且會有^ķ3塊乘法（在第一矩陣中的每個塊將被由ķ塊在第二矩陣相乘）。因此，複雜性復發是

T（N）= K T（N/K）+ Θ（N ）。

T（N）= Θ（N ^{日誌_ķ（K ）}）= Θ（N ）。

這與普通的矩陣乘法相同。顯然，它並沒有擊敗斯特拉森。

2016-10-03 06:52:41

「將你的矩陣分成k個塊...每個矩陣都有k^2個塊」？ –

@ScottHunter非常感謝！這是一個可怕的錯字。 –

不，這是一個輝煌的錯字:) –

回答