2

課題のために、数 n が O(log log n) 時間で 4 のべき乗であるかどうかをテストできるアルゴリズムを見つける必要があります。これにアプローチする方法がわかりませんし、どのデータ構造やアルゴリズムが適切かわかりません。この問題にアプローチする方法について何か提案はありますか?

4

6 に答える 6

6

ワード サイズがわかっている場合は、O(log log N) よりも優れた処理を実行できます。実際、O(1) では、4 つのマシン命令にコンパイルする必要があるものを使用して実行できます。たとえば、32 ビットの int を想定している場合は、次のようにすることができます。

int is_power_of_4(int x) {
    return ( (x & (-x)) & 0x55555554 ) == x;
}

ワード サイズが異なる場合は、定数を変更するだけです。

このx & (-x)トリックは、x の最下位 1 ビットのみの数値を返すよく知られたハックです。次に& 0x5554、2 の奇数乗をマスクし、x に他のビットが設定されている場合、元のデータとの比較は失敗します。

于 2013-10-26T20:26:23.070 に答える
2

数値は固定幅の整数として表されると仮定します。これにより、比較、加算、乗算などの基本的な演算を時間 O(1) で実行できます。

数値 n がある場合、その数値 n には O(log n) ビットが含まれていることに注意してください。b を数値のビット数とすると、必要な実行時間は O(log b) になります。言い換えれば、実行時間が数のビット数で対数になる関数を見つけたいと考えています。

数値が 4 のべき乗であるかどうかを確認しようとしているので、数値 k に対して数値が 4 kの形式を持っているかどうかを確認しようとしています。これを行うために使用できるアプローチの 1 つを次に示します。

  1. n より大きい数値が見つかるまで、4 1、4 2、4 4、4 8、4 16、...、4 2 xを計算します。これは、n が 4 の累乗である場合、4 0と 4 2 xの間に挟まれた 4 の累乗でなければならないことを意味します。このステップは、次の理由で O(log log n) 時間かかることになります: 数 n は 4 log 4 nと書くことができます。上記のプロセスは、4 2 x ≥ 4 log 4 nになるとすぐに終了し、2 x ≥ log 4になるとすぐに終了します。n、これは x ≥ log 2 log 4 n の場合に発生します。したがって、合計で O(log log n) 回の反復しかなく、各反復には O(1) の時間がかかります。

  2. [0, 2 x ]の範囲で二分探索を行い、 n = 4 kを満たす k の値を特定します。このステップの実行時間は O(x) になります。これは、サイズが 2 xの範囲でバイナリ検索に O(log 2 x ) = O(x) の時間がかかるためです。さらに、x = O(log n) であることがわかっています。ステップ (1) では、log 4 nの値を超えるまで指数を 2 倍にし続けました。これは、最悪の場合、x が 2 log 4 x になり、x = O(log n) になることを意味します。したがって、このステップには O(log log n) 時間もかかります。

ステップ (1) と (2) にはそれぞれ O(log log n) の時間がかかるため、全体の時間の複雑さは O(log log n) です。

注:この問題は、nの対数に関する「数当てゲーム」の一種と考えることができます。典型的な面接の質問は、「私は自然数 n について考えているので、推測してみてください」です。上記のアプローチのほとんどを使用して、O(log n) 時間で解決できます。この場合、機能する 4 の指数を推測しようとしているので、数値の対数に手順を適用して O(log log n) の実行時間を取得できます。

お役に立てれば！

于 2013-10-26T18:54:39.010 に答える
0

ここでは、マシン ポータブル ソリューションを提供します。このソリューションは、事前に計算された数値を必要とせず、マシンのビット幅に関する仮定も行いません。

bool isPowerOfFour(int num) {
    int s = ceil(sqrt(num));
    // s > 0 makes sure 0 is not power of four
    // 4^x -> 2^(2x) so sqrt of it should be 2^x all we need to do is to tell whether the sqrt is a power or two
    // but firstly we need to make sure sqrt(num) is an integer so we use s*s == num
    // then use (s&(s-1)) == 0 to tell whether it is a power of 2
    return s > 0 && s*s == num && (s&(s-1)) == 0; 
}
于 2016-07-11T07:57:37.880 に答える
0

マスクの使用に関して、携帯性が若干向上しました。

#include <stdio.h> 
#include <string.h>

int main ()
{
   int x;
   int mask;

   memset(&mask, 0x55, sizeof(int));
   scanf("%d",&x);

   if ((x) && ((x & (x-1)) == 0) && (x & mask))
       printf("Power of four\n");
   else
       printf("Not power of four\n");
   return (0);
}
于 2014-08-09T17:30:57.483 に答える