algorithm - 这两种位计数算法是否具有相同的时间复杂度?

下面是我在某个地方(忘记确切位置,可能是从this answer中)找到的一个算法,用来计算整数中设置的位数,即它的Hamming权重。

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)中运行的吗?
如果是的话,有没有一种方法可以区分这两者?似乎第一个应该在某些方面更好。

最佳答案

在这种情况下,以大O复杂度来看问题是没有意义的,因为变量中有固定数量的位。相反,您应该计算各个操作:
算法1:
按位ands:4
位移:4
加/减:3
乘法:1
算法2:
按位ands:32
位移:32
加/减:64
乘法:32
即使允许用额外的位移替换这些乘法,在第二个算法中也要做更多的工作。

本文翻译自 https://stackoverflow.com/questions/27844410/

网站遵循 CC BY-SA 4.0 协议,转载或引用请注明出处。

标签 algorithm big-o time-complexity hammingweight


相关文章:

python - 如果此字母基于此算法存在,如何弹出?

c - 如何计算从范围1到n的0或1的总外观?

java - 递归函数计算飞镖的可能光洁度

java - 算法的复杂度和效率:a [j] -a [i] i> = j

algorithm - Big O表示法Log Base 2或Log Base 10 [重复]

algorithm - 贪婪算法的复杂性

algorithm - O(N ^ N)是什么复杂度类?

algorithm - 具有最佳时间复杂度的搜索算法

java - 以下代码的增长顺序

algorithm - Floyd Warshall的复杂性