矩阵一些运算的时间复杂度

这里根据网上信息给出结论[1-4]：

矩阵乘积：时间复杂度为 $O(n^3)$
矩阵求逆：时间复杂度为 $O(n^3)$
矩阵本征值：时间复杂度为 $O(n^3)$

AI 生成补充（模型 GPT-4o）：

矩阵乘积 (Matrix Multiplication):
- 经典算法的时间复杂度是 (O(n^3))，其中 (n) 是矩阵的维度。
- Strassen 算法可以将时间复杂度降低到 (O(n^{2.81}))。
- 最优的矩阵乘法算法（例如 Coppersmith-Winograd 算法）具有 (O(n^{2.376})) 的时间复杂度，但在实际应用中由于常数项较大，常常并不如经典算法高效。
矩阵求逆 (Matrix Inversion):
- 经典算法（例如高斯消元法）的时间复杂度是 (O(n^3))。
- 使用 Strassen 算法进行矩阵乘法的求逆算法时间复杂度可以降至 (O(n^{2.81}))。
- 一些更复杂的算法可以在理论上达到更低的时间复杂度，但实际应用中常用的还是接近 (O(n^3)) 的算法。
矩阵本征值 (Matrix Eigenvalues):
- 求解矩阵本征值的常见算法（如 QR 分解法）的时间复杂度大约为 (O(n^3))。
- 对于对称矩阵，可以使用更高效的算法，比如 Jacobi 法，时间复杂度约为 (O(n^3))。
- 由于本征值问题通常涉及迭代方法，具体时间复杂度可能依赖于矩阵的性质和所需的精度。
总体来说，这些操作在大多数实际应用中仍然需要 (O(n^3)) 的时间复杂度。

Python代码验证：

import numpy as np
import matplotlib.pyplot as plt
import time



time_1 = np.array([])
time_2 = np.array([])
time_3 = np.array([])
n_all = np.arange(2,5000,200)  # 测试的范围
start_all = time.process_time()
for n in n_all:
    print(n)
    matrix_1 = np.zeros((n,n))
    matrix_2 = np.zeros((n,n))
    for i0 in range(n):
        for j0 in range(n):
            matrix_1[i0,j0] = np.random.uniform(-10, 10)
    for i0 in range(n):
        for j0 in range(n):
            matrix_2[i0,j0] = np.random.uniform(-10, 10)

    start = time.process_time()
    matrix_3 = np.dot(matrix_1, matrix_2)  # 矩阵乘积
    end = time.process_time()
    time_1 = np.append(time_1, [end-start], axis=0)

    start = time.process_time()
    matrix_4 = np.linalg.inv(matrix_1)  # 矩阵求逆
    end = time.process_time()
    time_2 = np.append(time_2, [end-start], axis=0)

    start = time.process_time()
    eigenvalue, eigenvector = np.linalg.eig(matrix_1)   # 求矩阵本征值
    end = time.process_time()
    time_3 = np.append(time_3, [end-start], axis=0)



end_all = time.process_time()
print('总共运行时间：', (end_all-start_all)/60, '分')

plt.subplot(131)
plt.xlabel('n^3/10^9')
plt.ylabel('时间（秒）') 
plt.title('矩阵乘积')
plt.plot((n_all/10**3)*(n_all/10**3)*(n_all/10**3), time_1, 'o-')

plt.subplot(132)
plt.xlabel('n^3/10^9')
plt.title('矩阵求逆')
plt.plot((n_all/10**3)*(n_all/10**3)*(n_all/10**3), time_2, 'o-')

plt.subplot(133)
plt.xlabel('n^3/10^9') 
plt.title('求矩阵本征值')
plt.plot((n_all/10**3)*(n_all/10**3)*(n_all/10**3), time_3, 'o-')

plt.rcParams['font.sans-serif'] = ['SimHei']  # 在画图中正常显示中文
plt.rcParams['axes.unicode_minus'] = False  # 中文化后，加上这个使正常显示负号
plt.show()

计算结果为（运算总时长约40分钟）：