c++ - 算法分析大O和正态表示法

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）我讨厌老师教不在书上的东西！

最佳答案

你要从头开始：你首先需要计算运行一个平均案例所需的时间多重：
在mmultiply中，首先看到的是一个从0到n-1的循环，它提供了：
T（MMultiply）=n*（T（在第一个循环中是什么）
现在你需要T（在第一个循环中是什么）因为在第一个循环中只有另一个循环，T（在第一个循环中的是什么）=n*T（在第二个循环中的是什么）
在第二个循环中只有一个对“dotproduct”的调用，因此，忽略“=”赋值，t（在第二个循环中的是什么）=t（dotproduct）。
要计算t（dotProduct），请逐行使用函数：
首次转让1
n表示循环
循环每次迭代3次（1次为“+=”操作，1次为对i的调用，i只执行一次操作）
所以T（点积）=1+n*3
在初始执行中替换t（dotproduct）将提供：
T（MMultiply）=n*n*（1+n*3）=3*n^3+n^2
所以
t（mmultiply）=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。