loglogN复杂性循环如何？

Question

我在这里几个问题考虑以下循环(让N = 8)

for(int i=1;i<N/2;i++){

  // this is O(logN)

}

N/2 = 4但是log(8)= 3(考虑基数为2)那么为什么上面的循环被认为是O(logN)

以及O(loglogN)循环如何？

PS:对不起我糟糕的数学概念

Answer 1

O(log n) 环:

for (i = 1; i <= n; i *= 2)

所以你i在每一步都加倍.基本上:

1. 增量=> O(n)
2. 加倍=> O(log n)
3. ??? =>O(log log n)

乘法后会发生什么？幂.所以这将是O(log log n):

for (i = 2; i <= n; i *= i) // we are squaring i at each step

注意:你的循环O(n)不是O(log n).与上述increment / double / exponentiate想法保持一致,您可以使用增量重写循环:

for(int i = 1; i < n; i += 2)

即使你增加更多,它仍然是增量,但仍然O(n).