矩陣乘法算法時間複雜度

我想出了這個矩陣乘法算法。我在某處讀到矩陣乘法的時間複雜度爲o（n^2）。但我想我的這個算法會給o（n^3）。我不知道如何計算嵌套循環的時間複雜度。所以請糾正我。矩陣乘法算法時間複雜度

for i=1 to n 
    for j=1 to n  
    c[i][j]=0 
    for k=1 to n 
     c[i][j] = c[i][j]+a[i][k]*b[k][j]

來源

2011-12-17 zedai

'b [i] [k]'看起來不對。我懷疑你希望在最後一行的RHS上有'c [i] [j] + a [i] [k] * b [k] [j]'這樣的東西。 – 2011-12-17 18:04:32

沒有它的正確。這裏c [i] [j]是結果矩陣 – zedai 2011-12-17 18:06:14

那麼，在這種情況下，你絕對不是在做矩陣乘法！注意，對於給定的'i'，你在'c [i] [j]'中爲每個'j'計算相同的結果，所以在你的輸出矩陣'c'中，所有的列都是相同的。你需要在最後一行用'b [k] [j]'替換'b [i] [k]'。 – 2011-12-17 18:18:21

天真的算法，這是你一旦你糾正它，如註釋中指出的那樣，是O（n^3）。

確實存在減少這種情況的算法，但您不太可能找到O（n^2）實現。我認爲最有效的實施問題仍然是開放的。

有關更多信息，請參閱此維基百科有關Matrix Multiplication的文章。

來源

2011-12-17 18:34:46

將m乘n矩陣乘以n乘p矩陣的標準方法的複雜度爲O（mnp）。如果所有這些對你來說都是「n」，那麼它就是O（n^3），而不是O（n^2）。編輯：在一般情況下它不會是O（n^2）。但是對於特定類型的矩陣有更快的算法 - 如果你知道更多，你可能會做得更好。

來源

2011-12-17 18:01:26

這是錯誤的。一般情況下有加速。 – jwg 2014-06-08 22:35:15

斯特拉森的算法？當然。 OP要求O（n^2），這在一般情況下是不可能的。這正是我所掌握的。 – 2014-06-09 11:38:27

使用線性代數，存在的算法實現比原始O更好的複雜性（n ）。 Solvay Strassen算法通過減少對每個2×2子矩陣所需的乘法的數量從8至7

最快已知矩陣乘法算法是Coppersmith-Winograd算法具有複雜度O（實現了爲O（n ^2.807）的複雜性n ^2.3737）。除非矩陣很大，否則這些算法不會導致計算時間的巨大差異。在實踐中，使用矩陣乘法的並行算法更容易，更快速。

來源

2011-12-18 06:36:08 viswanathgs

根據[Wikipedia]（https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm），2014年有一個矩陣乘法算法實現了O（n^2.3729），而Coppersmith-Winograd算法是最快至2010年。 – Garrett 2014-10-24 05:23:37

-1

在矩陣乘法中有3個for循環，我們正在使用，因爲每個for循環的執行需要時間複雜度O(n)。因此，對於三個循環，它變成O(n^3)

來源

2013-01-30 09:28:22 user2024721

矩陣乘法算法時間複雜度

回答

相關問題