该功能的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

该函数的大O不是恒定时间。

功能的大O将与功能math.log的大-O相同。这基本上取决于函数的实现。 （math.floor功能可以实现在恒定的时间）。

log函数通常使用泰勒级数展开计算，并且是O(M(n) * n^0.5)，其中M(n)是乘以两个n位数的复杂度。请致电link。

注：如果你想检查一个数是2电源，所有你需要做的就是下面的检查与二进制算术

高清pow_of_2（X）： 回报（（X & （x - 1））== 0）

基本上你需要检查在二进制表示中是否只有一位被设置为1。关于如何工作的更详细的解释是here。