对下面的 C++ 函数 MMultiply 的运行时间做一个理论分析。计算 MMultiply 作为 n 的函数的乘法次数,因为在这种情况下,n 是输入的大小/问题的大小。展示你的作品。用大 O 符号表示答案。
int I(int i, int j, int n)
{
return n * i + j;
}
int sProduct(const int A[],const int B[],int i, int j, int n)
{
int t = 0;
for( int k=0; k<n; k++ )
{
int d = A[ I(i,k,n) ] * B[ I(k,j,n) ];
t += d * d;
}
return t;
}
void MMultiply(const int A[], const int B[], int C[], int n)
{
for( int i=0; i<n; i++ )
for( int j=0; j<n; j++ )
C[ I(i,j,n) ] = sProduct(A, B, i, j, n );
}
发现答案是 O(n^3),但我不明白这是如何计算的。
MMultiply 中的外循环给出 n,内循环是 n,所以用乘法查看函数有 3......M(n)=n*n(....) 然后我迷路了关于如何查看其他函数。T(n) 和 C(n) 符号也让我失望......