C++实现n×n矩阵加减、相乘、转置的算法复杂度分析求助

1. 矩阵加法 #

实现代码：

for(i = 0; i < n; i++)
   for( j = 0; j < n; j++)
      a[i][j] = b[i][j] + c[i][j];

复杂度分析：两层循环每层执行n次，核心的加法赋值操作执行总次数为n²，单次操作为常数时间开销，因此时间复杂度为O(n²)。

2. 矩阵乘法 #

实现代码：

for( i = 0; i < n; i++)
   for(j = 0; j < n; j++)
      for(k = a[i][j] = 0; k < n; k++)
         a[i][j] += b[i][k] * c[k][j]; 

复杂度分析：这是朴素矩阵乘法实现，三层循环每层执行n次，核心的乘加操作执行总次数为n³，单次操作为常数时间开销，因此时间复杂度为O(n³)。

3. 矩阵转置 #

实现代码：

for(i = 0; i < n - 1; i++)
   for(j = i + 1; j < n; j++){
      tmp = a[i][j];
      a[i][j] = a[j][i];
      a[j][i] = tmp;
}

复杂度分析：这是原地转置实现，仅遍历矩阵上三角区域执行元素交换，总操作次数为n(n-1)/2，忽略常数系数后时间复杂度为O(n²)。

内容的提问来源于stack exchange，提问作者Hiếu Trung Vũ