这段伪代码while循环的时间复杂度（Big-O）是多少？求验证与详解

首先先帮你理清楚这段伪代码的逻辑：

• 先把变量i设为1
• 进入循环：只要i小于数组长度n，就重复做两件事：
  • 检查数组第i个位置的元素A[i]是不是0，如果是，立刻退出整个循环
  • 如果不是0，就把i翻倍（比如1变2，2变4，以此类推）

你的判断完全正确！下面给你拆解清楚： #

最好情况：O(1) #

当A[1]的值是0时，第一次进入循环就触发了终止条件，整个循环只跑了1次判断操作，没有多余的步骤。这种固定次数的操作，时间复杂度就是常数级的O(1)。

最坏情况：O(log(n)) #

最坏情况是所有被访问到的A[i]都不是0，循环会一直执行到i翻倍到不小于n才停止。
举个实际例子，假设n=10：

• i的变化是1→2→4→8→16，当i=16时，16≥10，循环结束，一共跑了4次。
• 从数学上看，i每次是2的幂次，我们需要找到最小的k使得2^k ≥n，也就是k=log₂(n)（向上取整）。这个次数和n的对数成正比，所以时间复杂度是O(log(n))。

内容的提问来源于stack exchange，提问作者aurora