Big O表示法作业 - 代码片段算法分析？ [英] Big O Notation Homework--Code Fragment Algorithm Analysis?
问题描述
对于家庭作业，我给了以下8个代码片段来分析并给出运行时间的Big-Oh表示法。如果我走在正确的轨道上，有人可以告诉我吗？
For homework, I was given the following 8 code fragments to analyze and give a Big-Oh notation for the running time. Can anybody please tell me if I'm on the right track?
//Fragment 1
for(int i = 0; i < n; i++)
sum++;
我在想片段1的O（N）
I'm thinking O(N) for fragment 1
//Fragment 2
for(int i = 0; i < n; i+=2)
sum++;
片段2的O（N）以及
//Fragment 3
for(int i = 0; i < n; i++)
for( int j = 0; j < n; j++)
sum++;
片段3的O（N ^ 2）
O(N^2) for fragment 3
//Fragment 4
for(int i = 0; i < n; i+=2)
sum++;
for(int j = 0; j < n; j++)
sum++;
片段4的O（N）
//Fragment 5
for(int i = 0; i < n; i++)
for( int j = 0; j < n * n; j++)
sum++;
片段5的O（N ^ 2）但是n * n让我失望了我不太确定
O(N^2) for fragment 5 but the n * n is throwing me off a bit so I'm not quite sure
//Fragment 6
for(int i = 0; i < n; i++)
for( int j = 0; j < i; j++)
sum++;
片段6的O（N ^ 2）以及
O(N^2) for fragment 6 as well
//Fragment 7
for(int i = 0; i < n; i++)
for( int j = 0; j < n * n; j++)
for(int k = 0; k < j; k++)
sum++;
片段7的O（N ^ 3）但是n * n再一次让我失望
O(N^3) for fragment 7 but once again the n * n is throwing me off
//Fragment 8
for(int i = 1; i < n; i = i * 2)
sum++;
片段8的O（N）
推荐答案
我认为片段5是O（n ^ 3），类似地片段7是O（n ^ 5）*。它看起来像片段8的O（log（n））。
I think fragment 5 is O(n^3), and similarly fragment 7 is O(n^5)*. It also looks like O(log(n)) for fragment 8.
对于n * n个问题，你必须执行循环体n * n次，所以它将是O（n ^ 2），然后你将其与其他代码的顺序复合。片段8实际上是计数器的两倍而不是递增它，所以问题越大，你需要做的额外工作就越少，所以它是O（log（n））
For the n * n problems, you have to execute the body of the loop n * n times, so it would be O(n^2), then you compound that with the order of the other code. Fragment 8 actually doubles the counter instead of incrementing it, so the larger the problem, the less additional work you have to do, so it's O(log(n))
* edit：片段7是O（n ^ 5），而不是我之前认为的O（n ^ 4）。这是因为j 和k 都从1变为n * n。对不起，我之前没有抓到这个。
*edit: Fragment 7 is O(n^5), not O(n^4) as I previously thought. This is because both j and k go from 1 to n * n. Sorry I didn't catch this earlier.
这篇关于Big O表示法作业 - 代码片段算法分析？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
