data-structures - この式の O が n の立方体であるのはなぜですか?

Question

この方程式の大きな O が n キューブである理由について質問があります。

else if(key == 'x')
   C = matrixMult(A, B);

どうもありがとう

Answer 1

結果の行列には n^2 エントリがあります。各エントリの計算は、n 個の積の合計によって実行でき、n^3 が得られます。

Strassen のアルゴリズムや既知の最速のアルゴリズムなど、より高速なアルゴリズムが存在するため、これは教科書のアルゴリズムに対してのみ有効です。