这个2次幂函数的"大O"

Question

以下功能的"大O"是什么？我的假设是它是O(log(n)),但我想仔细检查.该函数简单地确定其参数是否为2的幂.

def pow_of_2(x):
    a = math.log(x, 2)
    if a == math.floor(a):
       return True
    else:
       return False

Answer 1

函数的Big-O不是恒定时间.

函数的Big-O将与函数的Big-O相同math.log.这基本上取决于功能的实现.(该math.floor功能可以在恒定时间内实现).

该log功能是使用泰勒级数展开通常计算并是O(M(n) * n^0.5)其中M(n)是乘以两个n位数字的复杂性.

有关这方面的更多信息,请查看此链接.

注意:如果要检查数字是否为幂2,您需要做的就是使用二进制算法进行以下检查

def pow_of_2(x):return((x&(x - 1))== 0)

基本上,您需要检查1二进制表示中是否设置了一位.这是如何工作的更详细的说明是这里.