矩陣乘法：Java 實現與邏輯解析

題目描述

輸入兩個矩陣 A (m×s) 和 B (s×n)，計算其乘積 C = A × B (m×n)。

算法邏輯

矩陣乘法定義：C[i][j] = Σ_k=0^s-1 A[i][k] * B[k][j]。
三重循環：外層遍歷 A 的行 i，中層遍歷 B 的列 j，內層遍歷公共維度 k 累加乘積。

Java 完整實現

import java.util.Scanner;

public class MatrixMultiplication {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int s = in.nextInt();
        int n = in.nextInt();
        
        int[][] A = new int[m][s];
        int[][] B = new int[s][n];
        int[][] C = new int[m][n];
        
        for (int i = 0; i < m; i++)
            for (int j = 0; j < s; j++)
                A[i][j] = in.nextInt();
                
        for (int i = 0; i < s; i++)
            for (int j = 0; j < n; j++)
                B[i][j] = in.nextInt();
        
        // 矩陣乘法核心
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int sum = 0;
                for (int k = 0; k < s; k++) {
                    sum += A[i][k] * B[k][j];
                }
                C[i][j] = sum;
            }
        }
        
        // 輸出
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(C[i][j] + " ");
            }
            System.out.println();
        }
    }
}

優化方向

• 緩存優化： 交換循環順序 (i, k, j) 利用 B 的行訪問局部性，或使用分塊算法。
• 並行化： 外層循環可並行 (OpenMP / Java Stream)。
• Strassen 算法： 大矩陣可用 O(n^2.807) 算法。

複雜度

• 時間：O(m * s * n)
• 空間：O(m*s + s*n + m*n)