矩阵乘法伪代码最后一行时间复杂度函数正确性验证请求

首先，先把你提供的伪代码整理出来：

void matrixmult (int n, const number A[][], const number B[][], number C[][]) {
    index i, j, k;
    for(i = 1; i <= n; i++) // 原注释：the i for loop will run n + 1 times
        for(j = 1; j <=n; j++) // 原注释：the j for loop will run n(n+1) times
            C[i][j] = 0; // 原注释：this will run (n-1)n times
            for(k = 1; k <=n; k++) // 原注释：the k for loop will run (n-1)(n+1) times
                C[i][j] = C[i][j]+ A[i][k] * B[k][j]; // 原注释：this will run n((n-1)(n+1))
}

注意：这里伪代码有个缩进问题——for(k...)并没有被包含在for(j...)的循环体内（缺少大括号包裹），但从矩阵乘法的逻辑来看，这应该是笔误。正确的嵌套写法应该是：

void matrixmult (int n, const number A[][], const number B[][], number C[][]) {
    index i, j, k;
    for(i = 1; i <= n; i++) 
        for(j = 1; j <=n; j++) {
            C[i][j] = 0; 
            for(k = 1; k <=n; k++) 
                C[i][j] = C[i][j]+ A[i][k] * B[k][j]; 
        }
}

我们基于这个符合矩阵乘法逻辑的正确代码来分析时间复杂度：

逐行执行次数拆解 #

• 外层i循环：i从1到n，共执行n次（原注释的n+1是错误的——循环条件i<=n，从1到n刚好是n轮迭代）。
• 中层j循环：每一轮i循环里，j从1到n，总执行次数是n * n = n²次（原注释的n(n+1)错误）。
• C[i][j] = 0：每一轮j循环执行1次，总次数是n²次（原注释的(n-1)n错误）。
• 内层k循环：每一轮j循环里，k从1到n，总执行次数是n² * n = n³次（原注释的(n-1)(n+1)错误）。
• 最后一行的累加操作：每一轮k循环执行1次，所以总次数是n³次。

你的推导问题 #

你得出的T(n) = n(n-1)(n+1) = n³ - n是错误的，核心问题是对各层循环的执行次数判断失误：

1. 误判了外层i循环的执行次数，把终止条件的判断次数和循环体执行次数混淆了；
2. 忽略了三层循环是完全嵌套的关系（每一层都严格执行n次），错误引入了n-1的系数。

正确的时间复杂度 #

对于标准的n×n矩阵乘法，核心累加操作的精确执行次数是n³次，对应的渐近时间复杂度为O(n³)。

内容的提问来源于stack exchange，提问作者Mr.Coder