Python自定义power_iter函数的时间复杂度相关问题咨询

对应示例代码 #

import math

def power_iter(x,n) :
    for i in range(math.floor(math.log2(n))):
        x = x*x
        print(x)
    return math.pow(2,(n-math.pow(2,math.floor(math.log2(n)))))*x


print(power_iter(2,10))

问题1解答 #

math.floor(math.log2(n))与n-math.pow(2,math.floor(math.log2(n)))的时间复杂度确实为O(1)。

原因：Python标准库中math模块的对数、幂运算、取整函数都是底层用C语言实现的基础算术操作，针对常规范围内的数值，运算耗时不会随n的大小发生线性变化，属于固定耗时的常数操作。如果是超出常规精度范围的超大任意精度整数，运算耗时会有小幅波动，但常规开发场景下仍按O(1)判定。

问题2解答 #

你的判断是正确的，该代码整体时间复杂度为O(log₂n)，也可以简写为O(log n)，大O表示法中对数的底数属于常数因子，不会影响复杂度等级判定。

原因：代码中最核心的耗时部分是for循环，循环执行次数正好是math.floor(math.log2(n))次，循环体内的平方赋值、打印操作都是O(1)常数操作，循环结束后的return语句里的运算也都是O(1)操作，因此整体时间复杂度和循环次数成正比，即O(log₂n)。

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