40

ブライアン・カーニハンのアルゴリズムが整数のセットビット（1）をカウントするためにO（log N）を使用する理由を誰かが説明できますか？このアルゴリズムの簡単な実装は以下のとおりです（JAVA）

int count_set_bits(int n){
    int count = 0;
    while(n != 0){
        n &= (n-1);
        count++;
    }
    return count;
}

右端のセットビットを0になるまで1つずつクリアすることでどのように機能するかは理解できますが、O（log N）を取得する方法がわかりません。

4

3 に答える 3

32

このアルゴリズムは、設定されたビットと同じ数の反復を実行します。したがって、上位ビットのみが設定された32ビットワードがある場合、ループを1回だけ通過します。最悪の場合、ビットごとに1回通過します。整数nにはlog(n)ビットがあるため、最悪の場合はO(log(n))です。重要なビットで注釈が付けられたコードは次のとおりです（しゃれが意図されています）。

  int count_set_bits(int n){
        int count = 0; // count accumulates the total bits set 
        while(n != 0){
            n &= (n-1); // clear the least significant bit set
            count++;
        }
  }
于 2012-09-12T04:10:22.893 に答える
8

Nにはfloor（lg（N））+1つの有効ビットがあります。これは2を底とする対数です。nの1ビット数はせいぜいこれです。したがって、時間には漸近的な上限O（lg（N））= O（log（N））があります。

于 2012-09-12T02:56:28.483 に答える
5

この質問は、アルゴリズムの複雑さではなく、実際には大きなO表記でのNの意味に関するものです。

Nはデータのサイズを意味します。ただし、「データ」が単一の数値である場合は、データのサイズとして理解できるものを定義する必要があります。数値またはその表現の長さの値。

IMOのアルゴリズムはO（N）です。バイナリ表現で1をカウントするこの問題では、IMOに関連するデータのサイズは数値表現の長さであり、値、つまりビットストリームの長さではないためです。そして明らかな最悪のケースは、すべて1がN回の反復を行うことです。

ただし、Nの値をデータのサイズと見なすと、その表現の長さはlog（N）であるため、O（log（N））と言えます。

PSまた、大きなO表記は、任意に高いNのアルゴリズムを一般化する場合にのみ意味があります。このコードでは、Nはintサイズによって制限されているため、最大64ループの反復（64ビットintの場合）になるため、O（1）と言えます。

于 2016-11-08T13:45:17.177 に答える