java - 哪个代码在时间复杂度方面表现更好？

Question

下面是两个 java 代码，用于查找整数 N 中 1 的位数。

代码 1:

int count = 0;

while (N != 0) {
    N = N & (N - 1);
    count++;
}

return count;

代码 2:

int i = N;
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;

据我了解，第一种方法的复杂度为 O(N)，而第二种方法为 O(1)。所以第二个应该更好。

但是我不确定。

Answer 1

在谈论时间复杂度时，您必须小心。 Big-O 提供了渐近运行时间的度量，这意味着您需要测量任意大 N 的运行时间。大多数编程语言不提供(默认情况下)int任意大的类型，所以通常我们会稍微捏造一下这个问题并假装它们确实如此。

如果我们假设 int 可以尽可能大，那么第一个代码片段就可以工作。它每 1 运行一个循环在 N 的二进制表示中, 所以在最坏的情况下需要 log_2(N)迭代。所以它是 O(log N)。

如果 int，则第二个代码片段不起作用(也就是说，它会产生错误的结果)大于 32 位。如果我们想象int变大以支持更大的 N如果我们需要渐近分析，那么我们需要在程序中添加更多行来支持表示 N 所需的额外位。 .因为程序必须更改才能正确，所以实际上不可能进行渐近分析。该程序的任何特定版本都在 O(1) 时间内运行，但它不会为足够大的 N 生成正确的结果，因此它与第一个代码片段的比较不公平。

可以尝试修改第二个程序来适应N的大小通过使用循环而不是硬编码移位和添加。然后我认为它在 O(log(log(N))) 时间内运行，因为每个额外的移位都会使聚合的位数加倍。

要牢记的一件重要事情是，我们假设移位和按位运算仍然是 O(1)，无论我们正在制作 int。越来越大。这是在这些分析中很常见的假设，但在机器指令仅处理 4 或 8 字节数量的实际计算机上并非如此。

算法2的动态版本

您的问题是 Java，但这是 Python 中算法 2 的正确 O(log(log(N)) 版本(它确实具有任意大的整数)。如果您不知道，可以将其视为伪代码Python——但我认为无论如何这是相对可读的，将它转换为使用 java bignums 会使它更难理解。它计算 k ，表示 N 所需的位数，四舍五入到 2 的幂, 然后构造一个移位和掩码的列表来计算位。这需要 O(log(k)) 时间，并且由于 k=log(N)，整个算法需要 O(log(log(N) ) 时间(此处时间表示按位或算术运算)。

def generate_ops(k):
    ops = []
    mask = (1 << k) - 1
    while k:
        ops.append((k, mask))
        k >>= 1
        mask = mask ^ (mask << k)
    return reversed(ops)

def bit_count(N):
    k = 1
    while (1 << k) < N:
        k *= 2
    for shift, mask in generate_ops(k):
        N = (N & mask) + ((N >> shift) & mask)
    return N