这个2的幂函数的"Big 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

- user3121369

---

这似乎是 O(1)，因为它执行固定的计算，然后返回 True 或 False。 - Tim Biegeleisen

但是计算不是基于x的变量吗？@TimBiegeleisen - user3121369

该函数的时间复杂度为O(log(x))（因为将x转换为double类型的时间复杂度为O(log x)），但对于较大的x也会产生错误的结果。例如，pow_of_2(2 ** 1000)返回False。 - Paul Hankin

我认为你对运行时间分析有些困惑。该函数仅计算一个对数，然后返回结果。这是一个恒定的惩罚。如果你有一个循环或其他类型的结构，那么运行时间就不是恒定的了。 - Tim Biegeleisen

我和Tim在一起。O(1)。因为问题中没有任何东西需要“n”，所以它不可能是其他任何值。只有一个标量变量（x），而且你只对它进行了固定数量的操作（无论“x”取什么值）。 - mgilson

我怀疑OP询问的是关于x的复杂度，即将x加倍会如何影响函数返回的时间。如果不知道数学库如何计算对数函数，则无法回答这个问题。然而，通常情况下，较大的x会增加时间，但随着x的增长，惩罚会减小。它肯定不像O(x)那么糟糕，但肯定比O(1)差。我认为O(log(x))可能很接近。对于大x运行函数多次表明，时间在渐近意义下与log(x)成正比。 - Matthew

Answer 1

该函数的Big-O时间复杂度不是常数级别。

该函数的Big-O时间复杂度将与函数math.log的Big-O时间复杂度相同。这基本上取决于函数的实现。（math.floor函数可以在常数时间内实现）。

log函数通常使用泰勒级数展开计算，其时间复杂度为O(M(n) * n^0.5)，其中M(n)是两个n位数字相乘的复杂度。

更多信息，请参见此链接。

注意：如果要检查一个数是否是2的幂，则只需使用二进制算术进行以下检查：

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

基本上，您需要检查二进制表示中是否恰好有一个位设置为1。有关此操作方式的更详细说明，请参见此处。

- user1952500