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 のサイズに関係なく、反復回数は変わりません。

私が疑問に思っているのはこれです：

  • これら 2 つのアルゴリズムは、両方とも O(1) で実行できると本当に言えますか?
  • もしそうなら、2つを区別する尺度はありますか? 何らかの形で最初のものの方が優れているはずです。
4

4 に答える 4

4

この場合、変数には固定数のビットがあるため、大きな O の複雑さの観点から質問を見ることは意味がありません。代わりに、個々の操作をカウントする必要があります。

アルゴリズム 1:

  • ビット演算 AND: 4
  • ビットシフト: 4
  • 加算/減算: 3
  • 乗算: 1

アルゴリズム 2:

  • ビット単位 AND: 32
  • ビットシフト: 32
  • 加算/減算: 64
  • 掛け算: 32

これらの乗算を追加のビットシフトに置き換えることを考慮しても、2 番目のアルゴリズムではさらに多くの作業が行われています。

于 2015-01-08T16:19:18.780 に答える
1

これら 2 つのアルゴリズムは、両方とも O(1) で実行されると本当に言えますか?

はいぜったいに。入力のサイズに関係なく一定時間内に実行されるアルゴリズムは、O(1) であると言えます。

もしそうなら、2つを区別する尺度はありますか? 最初のものは何らかの形でより良いはずですか？

漸近的複雑度が同一のアルゴリズムを区別するのは、一定の要因です。これは、O(1) アルゴリズムだけでなく、漸近的な複雑さのアルゴリズムにも当てはまります。

これらのアルゴリズムに従って計算を実行するために必要な基本操作を合計することで、定数を計算できます。ループ外で実行される操作をカウントし、ループ内で実行される操作の数に、最悪の場合にループが実行される回数 (つまり 32) を掛けて加算します。

2 つのアルゴリズムの漸近的複雑度は同じですが、最初のアルゴリズムは定数係数がはるかに小さいと言われているため、2 番目のアルゴリズムよりも高速です。

于 2015-01-08T16:25:20.607 に答える
0

まあ、それは依存します。どちらも実際にはアルゴリズムではなく、実装であることに注意してください。実装では常に一定のビット数があるため、これは異なります。はい、常に - 配列サイズは定数によって制限されるため、bigint も定数によって制限されます。そんなことを考えても無駄なのは明らかです。

それでは、別の方法で見てみましょう。まず、実装ではなく概念アルゴリズムを検討してください。整数は現在 n ビット長であり、示したコードは n ビット形式に一般化されています。最初のステップは O(log n) ステップであるのに対し、2 番目のステップは O(n) です。しかし、これらの手順にはどのくらいの時間がかかりますか? それは抽象マシンに依存します。(プラトニックな意味で)「存在」する唯一の抽象マシンが RAM マシン、またはおそらくチューリング マシンであると偽るのは、スタックオーバーフローの伝統です。しかし、もっとあります。たとえば、PRAM では、必ずしも一定数の並列処理要素に制限されているわけではありません。

n ビットの加算は、十分なプロセッサ (つまり、少なくとも n) を備えた PRAM マシンでは O(log n) 時間かかりますが、ビット単位の操作は明らかに、少なくとも n プロセッサを備えた PRAM マシンでは O(1) しかかからないため、O が得られます。最初のアルゴリズムでは(log(n) 2 ) ですが、2 番目のアルゴリズムでは O(n log n) です。

しかし、さらに進んで、n ビットに対するすべての操作に一定の時間がかかると仮定することもできます。誰かがそれはできないとコメントすると確信していますが、実際には好きなことを想定できます（特にハイパーコンピューティングを調べてください）。O(log n) ビットの操作に一定の時間がかかるという通常の仮定も、考えてみればかなり奇妙です。とにかく、「nビット操作はO(1)」である場合、それは最初のアルゴリズムではO(log n)、2番目のアルゴリズムではO(n)です。

于 2015-01-08T16:48:04.613 に答える
0

f (n) = O (g (n)) は、一部の N > 0 および一部の c > 0 のすべての n ≥ N について、f (n) が c * g (n) 以下であることを意味します。重要になる可能性があります。あるアルゴリズムが n ナノ秒で実行され、別のアルゴリズムが n 時間で実行される場合、どちらも Big-O 表記で同じ時間になりますが、一方はわずかに (数千億倍) 高速です。明らかに、心配する必要はありません。ほとんど違いはありません。

PS。1 つのワードのビット数を数えることはほとんど重要ではありません。単語の配列のビットをカウントする場合、どちらのアルゴリズムも最適ではありません。

于 2015-01-08T16:17:16.827 に答える