1

自然数に対してのみ次のアルゴリズムを持つ: rounds(n)={1, if n=1; 1+rounds(ceil(n/2)), else} なのでプログラミング言語で書くとこうなる

int rounds(int n){
    if(n==1)
        return 1;
    return 1+rounds(ceil(n/2));
}

これには時間の複雑さ O(log n) があると思います

より良い複雑さはありますか？

4

2 に答える 2

1

アルゴリズムが反復的で数値が 2 進数であると考える場合、この関数は最下位ビットをシフト アウトし、シフト アウトされたのが 1 の場合は数値を 1 増やします。したがって、増分を除いて、数値のビット数 (つまり、最大の 1 の位置) をカウントします。数値が 1000... の形式の場合を除いて、インクリメントは最終的に結果を 1 増やします。したがって、ビット数 + 1、または数値が 2 の累乗の場合はビット数が得られます。マシンのモデルによっては、O(log n) よりも高速に計算できる場合があります。

于 2013-02-27T13:57:09.777 に答える
1

1から上に結果をリストすることから始めて、

rounds(1) = 1
rounds(2) = 1 + rounds(2/2) = 1 + 1 = 2

次に、ceil(n/2)が 2 の場合はrounds(n)3 になりn = 3ますn = 4。

rounds(3) = rounds(4) = 3

ceil(n/2)が 3 または 4 の場合、結果は 4 になり3 <= ceil(n/2) <= 4ます2*3-1 <= n <= 2*4。

round(5) = ... = rounds(8) = 4

続けてみるとわかるように

rounds(n) = k+2 if 2^k < n <= 2^(k+1)

誘導によって。

それを次のように書き換えることができます

rounds(n) = 2 + floor(log_2(n-1)) if n > 1 [and rounds(1) = 1]

n = 1数学的には、次のように書き換えることで一様に扱うこともできます

rounds(n) = 1 + floor(log_2(2*n-1))

ただし、固定幅型を使用している場合、最後の式はオーバーフローの可能性があります。

だから質問は

  • 数値を 1 と比較する速さ
  • 数字から1をどれだけ早く引くことができるか.
  • 正の整数の 2 を底とする対数 (の底) をどのくらい速く計算できますか?

固定幅の型、つまり境界のある範囲の場合、もちろんこれらはすべて O(1) 操作ですが、計算の複雑さは問題になりませんが、可能な限り効率的にすることにおそらく関心があるでしょう。

ネイティブ マシン タイプのint場合 (long通常はそうです)、整数の比較と減算は非常に高速なマシン命令であるため、問題になる可能性があるのは底 2 の対数だけです。

多くのプロセッサには、マシン タイプの値の先頭の 0 ビットをカウントするためのマシン命令があり、コンパイラがアクセスできるようにすると、基数 2 の対数を非常に高速に実装できます。そうでない場合は、古典的なビットハックの 1 つを使用して、再帰よりも高速なバージョンを取得できます。

たとえば、gcc と clang の十分に最近のバージョンには、命令がプロセッサ上に存在する場合はその命令にマップする__builtin_clz( __builtin_clzl64 ビット タイプの場合はそれぞれ)bsr*があり、提供されていない場合は、おそらく何らかのビット操作を使用する適切な実装があります。プロセッサによって。

バージョン

unsigned rounds(unsigned long n) {
    if (n <= 1) return n;
    return sizeof n * CHAR_BIT + 1 - __builtin_clzl(n-1);
}

命令を使用すると、 (私のボックスでは) 1 から 100,000,000 までのビットハックbsrqを計算するのに 0.165 秒かかりますrounds

unsigned rounds(unsigned n) {
    if (n <= 1) return n;
    --n;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n -= (n >> 1) & 0x55555555;
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
    return ((n * 0x01010101) >> 24)+1;
}

0.626 秒かかり、単純なループ

unsigned rounds(unsigned n) {
    unsigned r = 1;
    while(n > 1) {
        ++r;
        n = (n+1)/2;
    }
    return r;
}

1.865 秒かかります。

固定幅型を使用せず、任意精度の整数を使用すると、状況が少し変わります。単純なループ (または再帰) はまだステップを使用しΘ(log n)ますが、ステップにΘ(log n)は平均して時間がかかる (またはさらに悪い) ため、全体としてΘ(log² n)アルゴリズム (またはさらに悪い) が得られます。次に、上記の式を使用すると、定数係数が低くなるだけでなく、アルゴリズムの複雑さも低くなります。

  • 1 との比較は、適切な表現では一定時間で実行できますがO(log n)、妥当な表現では最悪のケースです。
  • 正の整数から 1 を引くO(log n)と、合理的な表現が得られます。
  • 基数 2 の対数 (の底) の計算は、一部の表現では一定の時間で実行でき、O(log n)他の合理的な表現では [2 のべき乗の底を使用する場合、私は半分慣れているすべての任意精度ライブラリを使用します。と; 彼らが10のべき乗ベースを使用した場合、それは異なるでしょう].
于 2013-02-27T17:18:52.740 に答える