#54624: 加速從O(n^3)到O(n^2.807)
samlin961112@gmail.com
(林哲甫)
1. 題目分析與前置檢查
矩陣相乘 A * B 的基本前提是：第一個矩陣 A 的列數 (Column) 必須等於第二個矩陣 B 的行數 (Row)。
- 假設 A 為 a x b 矩陣，B 為 c x d 矩陣。
- 檢查條件：若 b != c，則無法相乘，輸出 "Error"。
- 結果維度：若可相乘，結果矩陣維度為 a x d。
- 注意：題目提到的數值範圍很大，相乘結果會超過 32 位元整數，建議使用
long long型別。
2. Strassen 演算法核心原理
Strassen 演算法是一種分治法 (Divide and Conquer)。傳統做法需要 8 次遞迴乘法，而 Strassen 透過數學變換將乘法次數減少為 7 次。
A. 矩陣分割
將矩陣 A 與 B 各切分為 4 個子塊：
- A = [[A11, A12], [A21, A22]]
- B = [[B11, B12], [B21, B22]]
B. 計算 7 個中間變數 (P1 ~ P7)
- P1 = (A11 + A22) * (B11 + B22)
- P2 = (A21 + A22) * B11
- P3 = A11 * (B12 - B22)
- P4 = A22 * (B21 - B11)
- P5 = (A11 + A12) * B22
- P6 = (A21 - A11) * (B11 + B12)
- P7 = (A12 - A22) * (B21 + B22)
C. 組合結果 C
- C11 = P1 + P4 - P5 + P7
- C12 = P3 + P5
- C21 = P2 + P4
- C22 = P1 - P2 + P3 + P6
3. 實作關鍵技巧
補齊為 2 的冪次 (Zero Padding)
Strassen 演算法要求矩陣必須是 2^n x 2^n 的正方形。
- 由於本題矩陣不一定是正方形，實作時需找出 a, b, d 中的最大值。
- 將矩陣補零擴充到最接近的 2 的次方（例如 100x100 補成 128x128）。
- 計算完畢後，僅輸出原始範圍 (a x d) 的部分即可。
遞迴終止點 (Threshold)
雖然理論上可以遞迴到 1x1，但過多的遞迴會導致效能下降。實務上，當矩陣規模縮小到一定程度（例如 32x32 以下）時，切換回一般三層迴圈乘法效率會更高。
4. 效能與空間分析
- 時間複雜度：依據遞迴式T(n)=7T(n/2)+n^2，可由主定理算出T(n)=O(n^lgn)=O(n^2.807)
- 空間複雜度：由於遞迴時需要額外的子矩陣空間，空間開銷較大，約為 O(n^2)。
- 實際上因為巨大的常數，要在n非常大時才會較快，此外，實際上也有其他更快的演算法，同樣有非常大的常數，只有在處理超大運算，如AI時才會有有，最快是2024年的O(n^2.37155)