打印了几颗星星？ [英] How many stars are printed?

问题描述

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 2 N 相关的次数。

That's clearly a logarithm situation where the inner loop runs a number of times that is related to log2N.

而且，由于您正在另一个循环内运行，因此您乘单个复杂度即可得到 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).

这篇关于打印了几颗星星？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！