10 を底とする対数関数の複雑さはどれくらいですか?
30882 次
2 に答える
51
これは、対数を計算する値の定義域に大きく依存します。
IEEE double の場合、多くのプロセッサは 1 つのアセンブリ命令で対数を取ることができます。たとえば、x86にはFYL2XおよびFYL2XP1命令があります。通常、このような命令は固定基数で対数を取るだけですが、次の事実を利用して任意の基数で対数を取るために使用できます。
ログa b = ログc b / ログc a
2 つの対数を取り、その商を求めるだけです。
一般的な整数 (任意の精度の) の場合、繰り返し二乗法と二分探索を組み合わせて使用し、O(log log n) 算術演算のみを使用して対数を取得できます (数値を二乗するたびに指数が 2 倍になります。つまり、二乗しかできないことを意味します)。その値を超えてバイナリ検索を実行できるようになる前に、数 log log n 回)。フィボナッチ数を使ったかわいいトリックを使えば、O(log n) 空間だけでこれを行うことができます。2 進対数を計算している場合、ビット シフトを使用して短時間で値を計算できる便利なトリックがいくつかあります (ただし、漸近的な複雑さは同じです)。
任意の実数の場合、ロジックはより難しくなります。ニュートンの方法またはテイラー級数を使用して、特定の精度内で対数を計算できますが、これを行う方法に精通していないことを告白します。ただし、ほとんどの実数は IEEE double であり、その場合はより優れたアルゴリズム (またはハードウェア命令でさえ) があるため、実際にこれを行う必要はほとんどありません。
お役に立てれば！
于 2011-09-06T09:17:08.390 に答える