这段Python代码的时间复杂度是多少？面试相关困惑求解

结论 #

这段代码的时间复杂度是 O(log₁₀ x)（也可简化为O(log x)，因为对数底数在时间复杂度中属于常数因子，不影响阶数判断）。

具体解释 #

1. 循环次数的本质：
   代码中的while循环每次执行x = x // 10，相当于把x的十进制最后一位移除，x的数值每次缩小为原来的1/10。循环会一直执行到x变为0为止，循环次数等于x的十进制位数。

   • 比如x=1000（4位数），循环执行4次；x=10000000（8位数），循环执行8次。
   • 一个x的十进制位数等于floor(log₁₀x) + 1，忽略常数项后，循环次数的量级就是O(log₁₀x)。

2. 为什么O(n)的说法错误：
   如果把n定义为x的数值，O(n)意味着循环次数和x的数值成正比，但实际中x=1e7时循环仅执行8次，和1e7的数值完全不成正比，显然不符合代码的实际运行情况。

3. 取余运算的影响：
   你提到的取余%7是常数时间操作（O(1)），每次循环内的所有操作（整除、取余、条件判断、计数）都是固定时间完成的，不会改变整体时间复杂度的阶数。

面试时的解释思路 #

可以直接结合例子说明：

这段代码的循环次数等于输入x的十进制位数，比如x是k位数就循环k次。而k和log₁₀x是一个量级的，比如10^m的数有m+1位，所以时间复杂度是O(log₁₀x)。每次循环里的操作都是固定时间，所以整体复杂度由循环次数决定。

def code(x):
    count = 0
    while x > 0:
        x = x // 10
        result = x % 7
        if (result % 7 )== 0:
            count += 1
    return count

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