算法矩陣加法和乘法

設M，N爲整數，使得0 < = M，N < N.算法矩陣加法和乘法

定義：

Algorithm A: Computes m + n in time O(A(N)) 

    Algorithm B: Computes m*n in time O(B(N)) 

    Algorithm C: Computes m mod n in time O(C(N))

使用算法A的任意組合，B和C描述NXN矩陣加法和矩陣乘法的算法與Z/NZ中的條目。同時指出算法的運行時間big-O符號。

嘗試在溶液：

對於NXN除了在Z/NZ：令A和B是在Z/NZ NXN矩陣的條目A_ {IJ}和B_ {IJ}，使得I，J在{0,1，...，N}其中，i表示行，j表示矩陣中的列。此外，讓在A + B = C

Step 1. Run Algorithm A to get a_{ij} + b_{ij} = c_{ij} in time O(A(N)) 

Step 2. Run Algorithm C to get c_{ij} mod N in time O(C(N))

重複步驟1和2對所有的i，J {0,1，...，N}。

這意味着我們必須重複1,2 N^2次的步驟。因此，總的運行時間由

N^2[ O(A(N)) + O(C(N)) ] = O(N^2 A(N)) + O(N^2 C(N)) = O(|N^2 A(N)| + |(N^2 C(N)|).

對於乘法算法我只由乙算法替換步驟1，得到了總運行時間爲O(|N^2 B(N)| + |(N^2 C(N)|)就像上述估計。

請告訴我，如果我正確地處理這個問題，尤其是與大O符號。

謝謝。

來源

2015-02-24 Rose S

對於矩陣乘法你的算法是錯誤的。 'A * B_ {i，j}！= A_ {i，j} * B_ {i，j}'，事實證明，不能比'O（n^2logn）'更好的矩陣。 – amit 2015-02-24 08:42:17

您的matrix multiplication算法是錯誤的，並且會產生一個錯誤的答案，因爲A*B_{i,j} != A_{i,j} * B_{i,j}（有例外，對於一些獨特的情況下，像零矩陣）

我認爲這個問題的目的不是爲了實現高效的矩陣乘法，因爲這是一個很難但仍然研究的問題，所以我會回答矩陣乘法的天真實現。

對於任何指數I，J：

(AB)_{i,j} = Sum(A_{i,k} * B_{k,j}) = 
      = A_{i,1} * B_{1,j} + A_{i,2} * B_{2,j} + ... + A_{i,k} * B_{k,j} + ... + A_{i,n} * B_{n,j}

正如你所看到的，對於每一對i,j有n乘法和n-1加法ץ關於C invokations量 - 這取決於如果你需要調用它在每次添加後，或者只有一次完成後（這取決於您需要代表每個數字的位數），因此對於每對i,j - 您可能需要從1次到2n-1調用。

這使我們總的複雜性（假設爲每個2n-1個modolus（I，J）對，如果需要較少的如上面所解釋 - 相應地調整）：

O(n^3*A + n^3*B + n^3*C)

作爲邊注，一個良好的完整性檢查，顯示你的算法確實是不正確 - 它證明了矩陣乘法不能做優於Omega(n^2 logn)（Raz,2002），和目前最好的實現是~O(n^2.3)

來源

2015-02-24 08:56:03 amit

嘿，阿米特，非常感謝您的幫助。對於乘法算法，我們可以假設我們只需對每個'i，j'對進行一次模數。那麼，這會將算法的複雜度改變爲'O（n^2 * A + n^2 * B + n^2 * C）'嗎？另外，我的加法算法'O（| N^2 A（N）| + |（N^2 C（N）|）'的複雜性是否正確？再次感謝。 – 2015-02-24 11:19:32

@RoseS不，它會在這個這種情況下O（n^3 * A + n^3 * B + n^2 * C）。加法的複雜性對我來說似乎是正確的 – amit 2015-02-24 11:20:30

啊，是的，因爲我們還在做'n'乘法和'n-1'加法對於'n^2'條目。謝謝。 – 2015-02-24 11:25:07

算法矩陣加法和乘法

回答

相關問題