为何循环变量按常量倍乘除时，时间复杂度视为O(Logn)？

嘿，这个问题问到点子上了——其实本质是在搞懂「当循环每次把变量按固定倍数放大/缩小时，到底会执行多少次」，咱们用具体例子+数学逻辑拆解一下，就一目了然了。

先看一个最常见的例子：每次乘2的循环 #

比如这段代码：

i = 1
while i < n:
    # 这里是每次执行O(1)的操作
    i *= 2

咱们来数一下循环会跑多少次：

• 第1次：i=1
• 第2次：i=2
• 第3次：i=4
• ...
• 第k次：i=2^(k-1)

循环终止的条件是i >= n，也就是当2^(k-1) >= n的时候，循环就停了。解这个不等式的话，k-1 >= log₂(n)，也就是k ≈ log₂(n)。换句话说，循环执行的次数是以2为底n的对数级别。

反过来，每次除以常量的循环也一样 #

再看这段从n开始每次减半的循环：

i = n
while i > 1:
    # O(1)操作
    i = i // 2

同样数次数：从n到n/2，再到n/4，直到i变成1。这个过程需要的步数也是log₂(n)次——毕竟把n通过每次除以2降到1，和把1通过每次乘2升到n，步数是一样的。

为什么是logn，不是线性的O(n)？ #

关键区别在于变量的变化速度：

• 线性循环（比如i +=1）是逐次递增，要从1到n需要n次，次数和n成正比；
• 而常量倍缩放的循环是指数级变化，变量增长/减少的速度越来越快（或越来越慢），所以需要的次数是对数级的——比如n=1024时，线性循环要跑1024次，但乘2的循环只需要10次（2^10=1024），差距非常明显。

不管常量倍是多少，都统一写成O(logn) #

哪怕你把倍数换成3、5这类其他正数（只要不是1），比如每次乘3，那循环次数就是log₃(n)。但在大O表示法里，对数的底数是可以忽略的——因为log_b(n) = log₂(n)/log₂(b)，这是一个常数倍的关系，而大O只关注增长趋势，所以不管底数是多少，都统一记为O(logn)。

一句话总结 #

当循环变量以常量倍进行乘除时，循环执行的次数等于「把初始值通过常量倍缩放至终止条件所需的步数」，而这个步数正好符合对数函数的定义，因此时间复杂度被认定为O(logn)。

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