該功能的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。