大O表示法的算法复杂度

Question

请考虑以下代码段：

for(int index = 1;index < N;index*=2){
    int counter = 0;
    while(counter < N){
       counter++;
    }
}

根据Big Theta表示法确定其最佳和最差情况的运行时为N的函数。选项：

a）最佳情况：O（log（N））-最坏情况：O（N²）

b）最佳情况：O（N。log（N））-最坏情况：O（N。log（N））

c）最佳情况：O（N。log（N））-最坏情况：O（N²）

d）最佳情况：O（N）-最坏情况：O（N）

我在Java评估中看到了这个问题，我真的不知道正确的答案。我回答了选项D，但我不知道它是否正确。您能帮我吗？

Answer 1

这是O(NlogN)最好和最坏的情况。

内部循环每次重复完全相同的次数（即N次）时就会重复自身。

外部循环将自身重复logN次。

因此，如果将它们组合在一起，则counter的总增加次数是：

T(n) = N + N + ... + N = N*logN

这总共给您O(NlogN)时间。

Answer 2

我认为最佳和最坏情况的答案都是N log N

首先，没有短路。这意味着最好的情况必须与最坏的情况相同

第二，外部循环将运行log（N）次，因为每个循环中的索引都会加倍

第三，内循环从0累积到N-1，每次累加1。这就是N个操作

因此，N和N分别代表最佳和最差

Answer 3

内循环运行N次，因此外循环的每个循环为O(N)。外循环的索引呈指数增长，那么我们可以说它需要log(N)个周期。

将它们放在一起，由于没有任何“最佳”或“最差”条件，因此在两种情况下都将得到N log(N)，除了全部完成之外，没有其他方法可以退出该循环。