矩阵乘法最坏的情况下，最好的情况下和平均情况下的复杂性

Question

什么是（a）中最坏的情况下，（b）中最好的情况下，和（c）平均情况下，下面函数确实矩阵乘法

for i=1 to n do 
    for j=1 to n do 
     C[i,j]=0 
     for k=1 to n do 
      C[i,j]=C[i,j]+A[i,k]*B[k,j] 
     end {for} 
    end {for} 
end {for} 

的复杂性

你会如何证明复杂性？

Answer 1

i，j和k都去从1到n。

因此最好，平均和最坏的情况下是O（N * N * N）= O（N^3）

对于每个n可能i S的，有nj S和对于每个nj s，有nk s。 这给内循环的执行n * n * n。

Answer 2

为O（n^3），因为在每个嵌套循环，N是乘以N，因为你必须在嵌套循环3次，其完全处理整个N，那将是NXNXN = N^3