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可能i的s，都有n js，对于每个n js，都有n ks。这给出n * n * n了内部循环的执行。

Answer 2

O(n^3)，因为在每个嵌套循环上，N 乘以 N，因为你有一个嵌套循环 3 次，它完全处理整个 N，那将是NXNXN = N^3