算法运行时矩阵

Question

我很难弄清楚这个伪代码的紧界和下界。有人能帮忙吗？

Array S;
for i <-- 0 to n-1
  for j <-- 0 to n-1 
    for k <-- 0 to n-1 
       M[i][j] = M1[i][k]*M2[k][j]
return M

谢谢！

Answer 1

三个嵌套循环，没有提前结束的选项意味着复杂度为n^3，最佳和最坏情况相同。