LeetCode 231: 寻找数字是否为2的幂的时间复杂度

Question

这段代码的时间复杂度是多少，要找出这个数字是否是2的幂。

是否为 O(1)?

bool isPowerOfTwo(int x) {
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

LeetCode 231

Answer 1

在非正式的情况下，它是O(1)，因为代码需要一个约束的时间来运行。这不是恒定的时间，因为运行时间确实取决于输入（例如，如果 x 为0，函数快速返回），但它是有边界的。

更正式地说，它是模糊的，因为O(n)是为参数化为任意大的n的函数所定义的，而这里的 int 被限制在2^31或2^63范围内。通常在实际程序的复杂度计算中，这一点可以忽略（因为大小为2^31的数组非常大），但在这里，很容易想到你的函数接受范围之外的数字。

在实践中，复杂度理论家通常用两种方式来概括你的问题

• 要么假设 int 包含Theta(log n)位，而算术运算对Theta(log n)位的工作时间为O(1)(也就是说，随着输入大小的增加，内存单元和寄存器的大小也会变大)。这有时被称为 "字模型"。
• 或者假设算术运算只对位运算用O(1)时间。这有时被称为 "位模型"。

在字模型中，函数是O(1)。在位模型中，函数是O(log n)。

注意，如果你把 int 大int类型，那么你的函数肯定是O(log n)。

Answer 2

是的，它是O(1)，但是bitwiseAnd(10^9,1) bitwiseAnd(10,1)的时间复杂度是不一样的，尽管它们都是O(1)。实际上，你的方程本身涉及到4个基本运算，从它的运算能力来看，我们认为这是基本运算和单位运算。但实际上，这些基本运算也有32或64运算的代价，因为在大多数情况下，32或64位是用来表示一个数字的。所以这个O(1)的时间复杂度意味着最差的时间复杂度是32或64运算，因为32和64都是非常低的值，而且这些运算是在机器级别上进行的，所以这就是为什么我们不考虑这些单元步骤执行其功能所需要的时间。

Answer 3

是的，这段代码的时间复杂度是O(1)，因为运行时间是恒定的，不取决于输入的大小。