时间复杂度是 O(N) 还是 O(Log N)？

Question

i = 1;
while(i<N) {
   i*=2;
}

我认为上面代码的时间复杂度是 O(N) 但我不确定。如果您认为它是 O(Log N) 以及原因，请告诉我？

Answer 1

时间复杂度与周期数成正比。循环数正好等于Log(N)/Log(2)，其中 Log 是任意对数。或者只是Log2(N)，其中 Log2 是以 2 为底的对数。因此它是 O(Log N)。