矩阵乘法的计算复杂度

四个矩阵连乘的计算复杂度

参考知乎回答

https://www.zhihu.com/question/390206363

假设这四个矩阵的维度分别为
$\mathbf{A}(m\times n)$、
$\mathbf{B}(n\times p)$、
$\mathbf{C}(p\times q)$ 和
$\mathbf{D}(q\times r)$，那么它们的连续相乘 ABCD 的计算复杂度为:

$\mathcal{O}\left(mnp+mpq+mqr\right)$

调换矩阵乘法的顺序对之有影响。

列向量乘以行向量与行向量乘以列向量的对比

size= 1000;
% 生成列向量和行向量
column_vector = randn(size, 1);  % 1000行1列的列向量
row_vector = randn(1, size);     % 1行1000列的行向量

% 计时开始 - 列向量乘以行向量
tic;
result_col_times_row = column_vector * row_vector;
elapsed_time_col_times_row = toc;

% 计时开始 - 行向量乘以列向量
tic;
result_row_times_col = row_vector * column_vector;
elapsed_time_row_times_col = toc;

fprintf('列向量乘以行向量的运行时间：%f 秒\n', elapsed_time_col_times_row);
fprintf('行向量乘以列向量的运行时间：%f 秒\n', elapsed_time_row_times_col);

发现一个很奇怪的现象：当代码中size < 1000时，运算时间基本一致，而当代码中size > 1000时，列乘行的复杂度是行乘以列的10倍以上。

克罗内克积与直接乘积的计算复杂度对比

% 生成两个矩阵

size = 100
A = randn(size, size);  % 3x3 矩阵
B = randn(size, size);  % 4x4 矩阵

% 计算克罗内克积
tic;
C_kron = kron(A, B);
time_kron = toc;

% 直接乘积
tic;
C_direct = A .* B;  % 或者使用 C_direct = A * B，因为两个矩阵的大小相同
time_direct = toc;

fprintf('克罗内克积的运行时间：%f 秒\n', time_kron);
fprintf('直接乘积的运行时间：%f 秒\n', time_direct);

克罗内克积的运行时间：0.360322 秒
直接乘积的运行时间：0.015956 秒

差距巨大