1

对下面的 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) 符号也让我失望......

4

1 回答 1

3
  • i从 0 到 n，所以n总共是次。
  • 对于 each i，j从 0 到 n，所以n对于 eachi的n*n次数，总共是次数。
  • 对于 each j，k从 0 到 n，所以n对于 eachj的n*n*n次数，总共是次数。

行之有效的行，即：

int d = A[ I(i,k,n) ] * B[ I(k,j,n) ];
t += d * d;

执行n*n*n= O(n 3 ) 次。

还有另一条线可以工作。这里的任务：

C[ I(i,j,n) ] = sProduct(A, B, i, j, n );

被执行n*n= O(n 2 ) 次。所以整个算法是O(n 3 + n 2 )。随着n增长，n 2项是微不足道的，所以整个算法是 O(n 3 )。

这给了我们上限，即在最坏的情况下会发生什么。请注意，即使在最好的情况下，这些行仍然会执行 n 3次，因此您可以说下限也是 Ω(n 3 )。这意味着该算法是 Θ(n 3 )（即下限和上限相同）。

于 2013-10-08T07:11:37.333 回答