这两个位计数算法是否具有相同的时间复杂度？

Question

下面是我在某处找到的一个算法（忘记具体位置了，可能来自this answer）来计算一个整数中设置的位数，即它的汉明权重。

function hamming_weight($i)
{
    $i = $i - (($i >> 1) & 0x55555555);
    $i = ($i & 0x33333333) + (($i >> 2) & 0x33333333);
    return ((($i + ($i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

（我碰巧在 PHP 中很方便，但这实际上可以是任何语言。）
如果我没记错的话，这在 O(1) 中运行——毕竟没有分支。

下面是我自己写的一个位计数函数，除了可读性之外，我认为它较差：

function hamming_weight_2($i)
{
    $weight = 0;
    for ($k = 1, $s = 0; $k < 0xFFFFFFFF; $k *= 2, $s++)
    {
        $weight += (($i & $k) >> $s);
    }
    return $weight;
}

但是，它在哪些方面不如人呢？一开始我以为是"well there's a loop, so this should run in linear time"，后来我发现循环不依赖于输入的大小根本。无论 $i 的大小如何，迭代次数都保持不变。

我想知道的是：

这两个算法真的可以说都在 O(1) 内运行吗？
如果是，是否有区分两者的措施？看来第一个应该一些方面更好。

Answer 1

f(n) = O(g(n)) 表示f(n)小于或等于c * g(n)对于所有n≥N对于一些N>0和对于一些c> 0. c 分量可能很重要。如果一种算法在 n 纳秒内运行，而另一种算法在 n 小时内运行，则它们在 Big-O 表示法中具有相同的时间，但一个算法稍快（几千亿倍）。显然，这不是什么值得担心的事情。几乎没有任何区别。

PS。计算单个字中的位数很少很重要。对于计算字数组中的位，这两种算法都不是最优的。

Answer 2

在这种情况下，从大 O 复杂性的角度看问题没有意义，因为变量中的位数是固定的。相反，您应该计算单个操作：

算法一：

按位与：4
位移位：4
Additions/Subtracts: 3
乘法：1

算法二：

按位与：32
位移位：32
Additions/Subtracts: 64
乘法：32

即使允许用额外的位移位替换这些乘法，第二种算法的工作量也明显增加。

Answer 3

Can these two algorithms really be said to both run in O(1)?

当然，是的。任何在固定时间内运行且与其输入大小无关的算法都可以说是 O(1)。

If so, is there a measure that distinguishes the two? It seems the first one ought to be better in some way?

区分具有相同渐近复杂度的算法的是常数因子。这适用于任何渐近复杂度的算法，而不仅仅是 O(1) 算法。

您可以通过将根据这些算法执行计算所需的基本运算相加来计算常数。计数在循环外执行的操作，并将循环内操作的计数乘以循环在最坏情况下执行的次数（即 32）。

虽然这两种算法具有相同的渐近复杂度，但据称第一种算法的常数因子要小得多，因此比第二种算法更快。

Answer 4

好吧，这取决于。请注意，它们实际上都不是算法，它们是实现。这是不同的，因为在实现中你总是有一个恒定的位数。是的，总是——bigints 也受一个常量限制，因为数组大小受一个常量限制。很明显，这样想是没有用的。

所以让我们换个角度来看。首先，考虑概念算法而不是实现。整数现在是 n 位长，您显示的代码被概括为它们的 n 位形式。第一个将有 O(log n) 步骤，而第二个为 O(n)。但是这些步骤需要多长时间？这取决于你的抽象机。 Whosebug 的传统是假装 "existence" 中唯一的抽象机（在柏拉图意义上）是 RAM 机，或者可能是图灵机。但还有更多。例如 PRAM，您不必局限于恒定数量的并行处理元件。

n 位加法在具有足够处理器（因此，至少 n）的 PRAM 机器上需要 O(log n) 时间，按位运算显然在具有至少 n 个处理器的 PRAM 机器上只需要 O(1)，所以第一个算法的 O(log(n)²) 是第二个算法的 O(n log n)。

但你可以走得更远，假设对 n 位的所有操作都需要常数时间。我敢肯定有人会评论说你不能那样做，但你实际上可以假设你想要的任何东西（特别是查找超计算）。如果您考虑一下，通常假设 O(log n) 位上的操作需要常数时间也很奇怪。无论如何，如果 "n-bit operations are O(1)" 是您正在使用的，那么第一个算法是 O(log n)，第二个算法是 O(n)。

这两个位计数算法是否具有相同的时间复杂度？

Do these two bit-counting algorithms have the same time complexity?

algorithm

big-o

time-complexity

hammingweight