c++ - 算法分析大O和正常符号

Question

int I(int i, int j, int n) 
{ 
   return n * i + j;                                    >1
}
int DotProduct( int A[], int B[], int i, int j, int n )
{
   int t=0;                                             >1
   for(int k=0; k<n; k++ )                              > n+1              
      t += A[ I(i,k,n) ] * B[ I(k,j,n) ];               > n
   return t;                                            > n 
}
void MMultiply( int A[], int B[], int C[], int n ) 
{
   for( int i=0; i<n; i++ )                          > n+1
      for( int j=0; j<n; j++ )                       > (n)n+1
         C[ I(i,j,n) ] = DotProduct(A, B, i, j, n );  > see function above (n)(n)(3n+2)?
}

我不确定我是应该在旧帖子上发帖还是在新帖子上发帖，因为这很紧急(正在为期中学习)

反正我知道大O是n^3

(3n+2)(n)(n)+ (n+1)(n)+ (n+1) <我做对了吗？

arg 我讨厌老师教书上没有的东西!

Answer 1

您从头开始:您首先需要计算运行平均情况 MMultiply 所花费的时间:

您在 MMultiply 中看到的第一件事是从 0 到 n - 1 的循环，它为您提供:

T(MMultiply) = n*(T(what_is_inside_the_first_loop))

现在你需要 T(what_is_inside_the_first_loop)。由于在第一个循环中只有另一个循环，因此 T(what_is_inside_the_first_loop) = n*T(what_is_inside_the_second_loop)

在第二个循环中只有一次调用“DotProduct”，因此忽略“=”赋值，T(what_is_inside_the_second_loop) = T(DotProduct)。

要计算 T(DotProduct)，您需要逐行执行函数:

• 1 用于初始分配
• n 循环
• 循环的每次迭代 3 个(1 个用于“+=”操作，1 个用于每次调用 I - 它只执行一个操作)

所以 T(DotProduct) = 1 + n*3

在初始计算中替换 T(DotProduct) 可以得到:

T(MMultiply) = n * n * (1 + n*3) = 3*n^3 + n^2

所以

T(M乘) = 3*n^3 + n^2

大 O 表示法基本上只是将这个时间分配给特定的类(这是一个近似值)。最接近“3*n^3 + n^2”的类别是 n^3(因为 n^3 是最重要的成员)。所以 T(MMultiply) = O(n^3)。

你的计算几乎是正确的，但是你在 MMultiply 的前两行有一个“+ 1”的盈余，如果你对每一行注释处理该行所花费的时间，“t += A[ I( i,k,n) ] * B[ I(k,j,n) ]; "不取 n，只取 2。"return t"也一样，只取 1。