时间戳

首页 > 解决方案 > 印了多少颗星？

algorithm - 印了多少颗星？

问题描述

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)

我知道答案是 C)，但我们对为什么会这样感到困惑。

标签： algorithmbig-o

解决方案

A, B,也C不能D回答“打印了多少颗星？”这个问题。因为它们实际上都不是数字。但是，如果您的实际问题是“此代码的星印复杂性是多少？”，您只需检查两个循环 :-)

外循环运行N时间，所以这更容易一点。是N。

内循环从j（i所有外循环的平均值约为N / 2）开始，每次迭代将其减半。所以，如果i是1024，那将是大约十次迭代。如果512，大约九，256大约八，等等。

这显然是一种对数情况，内部循环运行多次与.log2N

而且，由于您在另一个循环中运行一个循环，因此您将各个复杂性相乘以O(N log N)获得（我们在复杂性分析中并没有真正使用对数底）。

推荐阅读