对于家庭作业,我给了以下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表示法作业
发布评论