2

下面是我在某个地方找到的算法（忘记了确切的位置，可能来自这个答案）来计算整数中设置的位数，即它的汉明权重。

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;
}

但是，它在哪些方面是劣质的？起初我认为“有一个循环，所以它应该在线性时间内运行”，但后来我意识到循环根本不依赖于输入的大小。无论 $i 的大小如何，迭代次数都保持不变。

因此，我想知道的是：

  • 这两个算法真的可以说都在 O(1) 中运行吗？
  • 如果是这样，是否有区分两者的措施？似乎第一个在某种程度上应该更好。
4

4 回答 4

4

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

算法1：

  • 按位与：4
  • 位移：4
  • 加法/减法：3
  • 乘法：1

算法2：

  • 按位与：32
  • 位移：32
  • 加法/减法：64
  • 乘法：32

即使允许用额外的位移来替换这些乘法，在第二种算法中也要做更多的工作。

于 2015-01-08T16:19:18.780 回答
1

这两种算法真的可以说都运行在 O(1) 中吗？

绝对没错。任何在固定时间内运行且与输入大小无关的算法都可以说是 O(1)。

如果是这样，是否有区分两者的措施？似乎第一个应该在某种程度上更好？

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

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

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

于 2015-01-08T16:25:20.607 回答
0

这得看情况。请注意，它们实际上都不是算法，它们是实现。那是不同的，因为在实现中你总是有一个恒定数量的比特。是的，总是 - bigints 也受常数限制，因为数组大小受常数限制。显然，这样想是没有用的。

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

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

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

于 2015-01-08T16:48:04.613 回答
0

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

PS。计算单个字中的位数很少重要。为了计算字数组中的位，两种算法都不是最佳的。

于 2015-01-08T16:17:16.827 回答