while 循环中 n/2 的大 O 表示法

Question

我不熟悉数据结构和类似的东西。

请教一个问题，我们如何确定这个过程的Big-O记法值：

while(n%2==0){
   console.log(2);
   n=n/2;
}

什么是大 O 表示法？先谢谢了。

Answer 1

如果n奇数则不执行循环。如果 n 是偶数，则需要 log2n（ 即 以 2 为底的对数）迭代，直到循环停止。它是 log2n 因为 n 在每个循环迭代中减少一半 (i.e., n=n/2;).

假设 console.log(2); 花费 c 时间，整体复杂度为 O(logn)。