java - 矩阵乘法大O表示法

Question

我有一个关于这段代码的最佳情况和大 O 表示法中最坏情况的问题。从我的角度来看，这两种情况都应该是 O(n^3)，但有些人不同意。

public int [][] multiply (int [][] A, int 
 [][] B, int n) {   
int [][] C = new int[n][n]; - 1 ( ignored )
for(int i=0; i<n; i++) {        - n 
  for(int j=0; j<n; j++) {  - n 
     if(A[i][j ]!=0) {  - 1 ( ignored )
         for (int k=0; k<n; k++) {   - n
              C[i][k] += A[i][j]*B[j][k]; - 
        }
      }
     }
   }
 return C; 

}

Answer 1

在平均情况和最坏情况下，矩阵乘法确实需要 O(n^3) 时间来运行。对于尺寸分别为 m x n 和 n x p 的 2 个矩阵，总共将进行 mnp(或为简单起见，为 n^3)计算，结果矩阵中的每个条目都会进行一次计算。至于最好的情况，这取决于你的程序在看到至少一个矩阵是零矩阵(矩阵中的所有条目都是 0)时会做什么。如果它可以发现零矩阵，那么您可以短路程序。在这种情况下，运行时间将为 O(n^2)(最多只需扫描几个 n x n 矩阵)，这是矩阵乘法可以实现的最佳时间。如果这种优化不可用，则无论如何，程序的运行时间都将是 O(n^3)。无论哪种方式，由于 Big-O 表示法的定义，您仍然可以说最好的情况是 O(n^3)，但这对大多数人来说并不感兴趣。