算法分析-大O

Question

印了多少颗星星？(选择最小的正确估计。) 对于(int = 0；i

1. O(对数N)
2. O(N)
3. O(N对数N)
4. O(N^2)

我有点困在这个问题上，我想是A还是D，但我不确定。

我知道Big表示法是如何工作的，但是当你乘以2时，我对内环中的增量更困惑。我认为它是A是因为外循环是对数(？)，但正如我所说的，我对内环不太确定。提前谢谢你

Answer 1

解释

外部循环生成N / 2迭代。对于每次迭代，内部循环都会上升到N / 2，但会按照2 * j的步骤进行。也就是说，您可以通过N / 2步骤到达log_2(N / 2)。

示例

取64号码。我们从1开始，在每次迭代中乘以2：

 1
 2
 4
 8
16
32
64

我们通过64步骤到达6。事实上，64就是2^6。所以log_2(64)是6。

解决方案

因此，总的来说，您有来自外部循环的N / 2迭代，每次生成内部循环的log_2(N / 2)迭代。这使得

N / 2 * log_2(N / 2)

执行打印行的总数。因此，3. O(N log N)是正确的答案。

而且，由于它很大-O，该算法也运行在4. O(N^2)中。然而，3. O(N log N)是最小的正确估计。

Answer 2

当你乘以2的时候，我对内环中的增量更困惑。

当您从1开始并继续将变量乘以2时，需要log(N) (base 2)步骤才能到达N。因此，内部循环的复杂性是O(log(N/2)，它相当于O(log(N) - log 2) = O(log(N))。

我认为它是A的原因是外循环是对数的.

另一方面，外部循环是O(N/2) = O(N)，因为i在每一步都在由1增加，它需要N/2，直到i等于N/2为止。

由于内循环不依赖于外部循环，所以在这种情况下，我们可以将复杂性乘以，并说总的复杂性将是O(N*log(N))。

因此，正确的选项是c。