-1

以下の関数リターンの時間計算量を計算しようとしています-

int isPowerof2(unsigned int num)
{
     if(((~num)&1) == 1)
          return 1;
      return 0;
}

O（1）である必要があると思いますが、否定の複雑さはわかりません。誰かがこれの複雑さを特定する方法を理解するのを手伝ってくれませんか。ありがとう！

編集-単一の数値の場合、それをn個の入力と見なし、関数が2の累乗をチェックするとしたら、その場合の複雑さはどうなるでしょうか。

4

2 に答える 2

6

2進数で表される2の累乗には、正確に1つのビットが設定され、その他はすべてゼロです。

1を引くと、右端のビットを含むすべてのビットが反転します。

110101100 - 1=> 110101011 (in the case of zero, all bits get inverted)

が2の累乗であるnum & (num - 1)場合にのみ、ゼロと評価されると仮定します。num

numが実際に2の累乗である場合、合計で1つのビットが設定されます。1を引くと、そのビットは0になり、すべてのビットがその右側に1に設定されます。

したがって、セットビットnumを共有するnum - 1 ことはできません。したがって、num & (num - 1)0と評価されます。

が2の累乗でnumはない（ゼロではない）場合は、少なくとも2ビットが設定されています。1を引くと、右端のセットビットのみが変更され、その右のセットビットだけが変更され、他のビットは影響を受けません。

したがって、最大で1セットのビットnumを共有します。ゼロではなく、2の累乗ではないため、ゼロと評価することはできないnum - 1と結論付けます。num & (num - 1)num

したがって、正しいチェックは次のとおりです。num && !(num & (num - 1))

複雑さ：通常のコンピューターでは、すべての二項演算は一定時間で発生します。一定時間の演算が一定量あるため、関数全体が一定時間で返されますO(1)。

その関数を呼び出すときは、n呼び出すたびに一定時間の作業を行います。2n倍になると、作業量が2倍になります。したがって、その場合の複雑さはですO(n)。

于 2013-01-26T10:08:44.120 に答える
1

最新のプロセッサは、マシンワードサイズの整数に対して、それらの整数の値に関係なく、一定数のクロックで基本的な算術演算と論理演算を実行します。したがって、関数内のこれらの操作はすべてO（1）であり、操作の数は固定されているため、関数全体がO（1）になります。

ところで、この関数は、指定された数値が2の累乗であるかどうかを判断しません。この関数は、の最下位ビットのみを調べるため、2の倍数であるかどうかを判断しますnum。

2の累乗の正しいチェックは、次のようになります。

int isPowerof2(unsigned int num)
{
  return (num != 0) && ((num & (num - 1) == 0);
}
于 2013-01-26T04:13:55.503 に答える