问题描述
for(int i = 0; i < N; i = i+1)
for(int j = i; j > 0; j = j/2)
StdOut.print("*");
以下是可能的答案：
A）O（log N） ，
B）O（N），
C）O（N log N），
D）O（N ^ 2）
The following are the possible answers:
A) O(log N),
B) O(N),
C) O(N log N),
D) O(N^2)
我知道答案是C），但我们对此感到困惑。
I know that the answer is C), but we are confused of why that is.
推荐答案
A ， B ， C 均不 D 可以回答打印多少颗星星？这个问题。因为它们实际上都不是数字。但是，如果您的 actual 问题是此代码的繁星印刷是什么？，则只需检查两个循环：-）
Neither A, B, C nor D can be an answer to the question "How many stars are printed?" because none of them are actually numbers. However, if your actual question is "What's the stars-printed complexity of this code?", you need to just examine the two loops :-)
外部循环运行 N 次，因此更简单。它是 N 。
The outer loop runs N times so that's the easier bit. It's N.
内部循环从 j 开始 i （在所有外部循环中的平均值约为 N / 2 ），并在每次迭代时将其减半。因此，如果 i 为 1024 ，则大约需要十次迭代。如果 512 约为9， 256 约为8，依此类推。
The inner loop starts j at i (which averages out over all the outer loops to be about N / 2), and halves it for each iteration. So, if i was 1024, that would be about ten iterations. If 512, about nine, 256 about eight, and so on.
这显然是对数情况，其中内部循环运行与 log N 相关的次数。
That's clearly a logarithm situation where the inner loop runs a number of times that is related to logN.
而且，由于您正在另一个循环内运行，因此您乘单个复杂度即可得到 O（N log N ）（我们在复杂度分析中并未真正使用对数底）。
And, since you're running one loop within the other, you multiply the individual complexities to get O(N log N) (we don't really use the logarithm base in complexity analysis).
这篇关于打印了几颗星星？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！