算法分析bigO和正常表示法
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 我讨厌老师教书上没有的东西！
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)?
}
im not sure if i should post on the old post or a new one so ill post on a new one just because this is urgent ( studying for a midterm)
anyways i know the big O is n^3
(3n+2)(n)(n)+ (n+1)(n)+ (n+1) < did i do this right?
arg i hate when teacher teaches something that is not on the book!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你从头开始：你首先需要计算运行平均情况 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 （点积）。
要计算 T(DotProduct)，请逐行使用函数：
因此 T(DotProduct) = 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。
You start from the beginning: you first need to calculate the time it takes tu run an average case MMultiply:
The first thing you can see in MMultiply is a loop from 0 to n - 1, that gives you:
T(MMultiply) = n*(T(what_is_inside_the_first_loop))
Now you need T(what_is_inside_the_first_loop). As you only have another loop inside the first loop, T(what_is_inside_the_first_loop) = n*T(what_is_inside_the_second_loop)
Inside the second loop is only a single call to "DotProduct" so, disregarding the "=" assignment, T(what_is_inside_the_second_loop) = T(DotProduct).
To calculate T(DotProduct), you take the function line-by-line:
so T(DotProduct) = 1 + n*3
replacing T(DotProduct) in the initial ecuation gives you:
T(MMultiply) = n * n * (1 + n*3) = 3*n^3 + n^2
so
T(MMultiply) = 3*n^3 + n^2
the big O notation basically just assigns this time to a specific class (it's an approximation). The class which approximates "3*n^3 + n^2" best is n^3 (since n^3 is the most significant member). So T(MMultiply) = O(n^3).
Your calculations were almost right, but you had a "+ 1" surplus on the first two lines of MMultiply and, if you commented on each line the time it takes to process that line, "t += A[ I(i,k,n) ] * B[ I(k,j,n) ]; " does not take n, it only takes 2. Same goes for "return t", it takes only 1.
简单的做法：
N^32N^3simple approach:
N^32N^3