algorithm - 基本的な算術演算のBigOの複雑さ

Question

乗算、平方根、対数、スカラー、行列積などの基本的な算術演算の広範なアルゴリズムのBig-Oの複雑さは何ですか？

Big-Oの複雑さの点ではより効率的であるが、実際のソリューションではあまり普及していない（たとえば、一般的なソフトウェアライブラリに実装されていない）エキゾチックなアルゴリズムはありますか？

score 18 · Accepted Answer

正方行列の行列積：

O（N ^2.38）Coppersmith–Winogradアルゴリズムもありますが、隠された定数が大きいため、広く普及しているとは思いません。

Big-int乗算：

2008年に公開されたnlogn・2 ^{O（log * n）}アルゴリズムもありますが、それは新しすぎて普及できませんでした。

通常、ナイーブな方法は通常のサイズの入力には十分です。

score 6 · Accepted Answer

入力サイズは通常固定されているため（つまり、32ビットまたは64ビット）、最も単純な操作はO（1）と見なされます。

通常の状態では、入力の「サイズ」に関係なく、プラットフォームは乗算、平方根、対数などに対してまったく同じ操作を実行します（つまり、int a=0;およびintb=Int32.MaxValueは両方とも32ビットです）。整数）。

行列や任意精度の数値を表現し始めると面白くなりますが、誰かがすでにウィキペディアの要約をリンクしているので、それについては説明しません。

Schönhage–Strassenを使用して「通常の」小さな数を乗算しないでください。泣きます。アルゴリズムがO（n ²）であるからといって、それが悪いことを意味するわけではありません。特に、nがほとんどの場合²⁵または²⁶の場合はそうです。

score 5 · Accepted Answer

操作には複雑さはありませんが、アルゴリズムには複雑さがあります。たとえば、さまざまな平方根アルゴリズムがあり、それらはさまざまな複雑さを持ちます。

score 1 · Accepted Answer

平方根と対数はさまざまな方法で実装でき、複雑さに大きく影響します（必要な精度によって判断されます）。

それらがルックアップテーブル（およびある種の補間）で実装されている場合、より高い精度が要求されるため、メモリ要件は実際に爆発しますが、複雑さは、配列内の値をルックアップし、場合によっては補間を適用することです。

より一般的には、それらはシリーズ定義によって実装されているようです。必要な精度に達するまで、ステートメントを何度も繰り返すか繰り返します。ここでは、より高い精度が必要になるため、ラウンド数が非常に多くなる可能性があります。また、計算自体も精度の向上の影響を受けます。

score 1 · Accepted Answer

任意の長さの整数について、 BigIntegerを見てください。O(log K)入力のサイズ、つまりビット数（通常は数値のビット）に関して、すべてにコストがかかりますK。N以下のビット数に使用します。

たとえば、足し算と引き算はになりO( N )ました。乗算はO( N^2 )（ナイーブ）またはO( n (log n)^(2+epsilon) )FFTを使用します。

他のアルゴリズムには、O( N )乗算を行う「べき」関数が含まれます。（今を除いて、各乗算にはコストがかかります！）

また、BigDecimalsには追加の複雑さがあります。これは、任意の長さの10進数に相当し、より基本的な操作のいくつかを超えて、いくつかのこともより興味深いものです（特に、必要な精度を把握したい場合）。Javaの実装を見ることができます。

score 0 · Accepted Answer

整数乗算も行うフーリエ型アルゴリズムがあります（Schonhage-Strassen）

整数乗算に対して通常よりもわずかに優れたシュトラッセンのアルゴリズムのバージョンがあると思いましたが、今考えてみると、それは単純なものと同じになります...

足し算と引き算はほとんど、足し算と引き算だけです。分割と平方根はおそらく興味深いですが...

また：これまでのところ、誰もがINTEGER演算について話していることに注意してください。フロート/ダブルに到達すると、すべてのベットがオフになります。それからあなたは数値解析の世界に入ります、そしてそれはそれ自身の分野全体です...

score 0 · Accepted Answer

膨大な数のビットの除算と平方根は、乗算ほど複雑ではありません。どちらの演算でも、単純な古いニュートン反復は、ニュートン反復が乗算のみを持つように配置できます。各ステップで正しい桁数が2倍になるため、各ステップでの計算の精度を2倍にすることができます。

7 に答える 7