matrix - 行列の乗算のワーストケース、ベストケース、および平均ケースの複雑さ

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可能なisのそれぞれにsがあり、sのn jそれぞれにn jsがありますn k。これによりn * n * n、内部ループが実行されます。

Answer 2

O（n ^ 3）、ネストされたループのそれぞれで、NにNが乗算されるため、ネストされたループが3回あり、N全体を完全に処理するため、NXNXN = N^3になります。