python实现分治法矩阵乘法

分治法矩阵乘法是一种有效的算法，可以将两个矩阵相乘的时间复杂度从 $O(n^3)$ 降低到 $O(n^{log_2 7})$。下面是 Python 实现：

def matrix_multiply(A, B):
    n = len(A)
    C = [[0 for j in range(n)] for i in range(n)]

    if n == 1:
        C[0][0] = A[0][0] * B[0][0]
    else:
        # 将矩阵分成四个子矩阵
        A11, A12, A21, A22 = partition_matrix(A)
        B11, B12, B21, B22 = partition_matrix(B)

        # 递归计算子矩阵的乘积
        C11 = add_matrix(matrix_multiply(A11, B11), matrix_multiply(A12, B21))
        C12 = add_matrix(matrix_multiply(A11, B12), matrix_multiply(A12, B22))
        C21 = add_matrix(matrix_multiply(A21, B11), matrix_multiply(A22, B21))
        C22 = add_matrix(matrix_multiply(A21, B12), matrix_multiply(A22, B22))

        # 组合子矩阵的乘积
        for i in range(n // 2):
            for j in range(n // 2):
                C[i][j] = C11[i][j]
                C[i][j + n // 2] = C12[i][j]
                C[i + n // 2][j] = C21[i][j]
                C[i + n // 2][j + n // 2] = C22[i][j]

    return C

def partition_matrix(A):
    n = len(A)
    A11, A12, A21, A22 = [], [], [], []

    for i in range(n // 2):
        A11.append(A[i][:n // 2])
        A12.append(A[i][n // 2:])
        A21.append(A[i + n // 2][:n // 2])
        A22.append(A[i + n // 2][n // 2:])

    return A11, A12, A21, A22

def add_matrix(A, B):
    n = len(A)
    C = [[0 for j in range(n)] for i in range(n)]

    for i in range(n):
        for j in range(n):
            C[i][j] = A[i][j] + B[i][j]

    return C

这里的 `matrix_multiply` 函数用于计算两个矩阵的乘积，`partition_matrix` 函数将一个矩阵分成四个子矩阵，`add_matrix` 函数用于将两个矩阵相加。注意到如果矩阵的大小为 $1 \times 1$，则直接将它们相乘即可。否则，将两个矩阵分成四个子矩阵并递归计算它们的乘积，然后组合子矩阵的乘积得到最终结果。

使用示例：

A = [[1, 2],
     [3, 4]]
B = [[5, 6],
     [7, 8]]

C = matrix_multiply(A, B)

print(C)

输出结果为：

[[19, 22], [43, 50]]