漸近最適アルゴリズム

コンピュータサイエンスでは、大まかに言えば、大きな入力に対して、最善のアルゴリズムよりも最悪の場合、一定の係数（入力サイズとは無関係）でパフォーマンスが低下する場合、アルゴリズムは漸近的に最適であると言われます。これは、ビッグオー記法が広く使用されている結果として、コンピュータサイエンスの研究でよく見られる用語です。

より正式には、問題が特定のリソースのΩ( f ( n ))を必要とすることが証明され、アルゴリズムがO( f ( n ))のみを使用することが証明されている場合、アルゴリズムは特定のリソースに関して漸近的に最適です。

これらの証明には、特定の計算モデル、つまり入力データで許容される操作に対する特定の制限の仮定が必要です。

簡単な例として、すべての比較ソートでは、平均および最悪の場合で少なくともΩ( n log n )回の比較が必要であることが知られています。マージソートとヒープソートは、 O( n log n )回の比較を実行する比較ソートであるため、この意味で漸近的に最適です。

入力データに比較に加えてアルゴリズムの構築に利用できる事前特性がいくつかある場合、漸近的に高速なアルゴリズムが実現できる可能性があります。たとえば、 N個のオブジェクトが範囲[1, N ]の整数であることがわかっている場合、バケットソートなどによってO( N )時間でソートできます。

アルゴリズムが漸近的に最適であるということは、入力が十分に大きい場合、定数倍以上でそのアルゴリズムを上回るパフォーマンスを発揮するアルゴリズムがないことを意味します。このため、漸近的に最適なアルゴリズムは、研究において「最終段階」と見なされることが多く、劇的に改善することができない結果の達成と見なされます。逆に、アルゴリズムが漸近的に最適でない場合は、入力のサイズが大きくなるにつれて、アルゴリズムのパフォーマンスが最良のアルゴリズムよりもますます悪くなることを意味します。

実際には、漸近的な利点がなくても、パフォーマンスの優れたアルゴリズムを見つけることは有用です。新しいアルゴリズムには、特定の入力に対するパフォーマンスの向上、リソースの使用量の削減、記述と実装の簡素化などの利点もあります。したがって、漸近的に最適なアルゴリズムが必ずしも「最終目的」であるとは限りません。

漸近的に最適なアルゴリズムは重要な理論的結果ですが、多くの実際の状況では漸近的に最適なアルゴリズムが使用されない可能性があります。

• この方法は、実際の入力サイズの範囲を超えたn (どのコンピュータ ストレージ システムに収まらないビット数の入力など) に対してのみ、より一般的に使用される方法よりも優れたパフォーマンスを発揮します。
• これは複雑すぎるため、検討中の入力サイズの範囲では、これを正しく理解して実装することの難しさが潜在的な利点を上回ります。
• 実際に遭遇する入力は、より効率的なアルゴリズムを持つ特殊なケース、または最悪のケースでは時間の問題を伴うヒューリスティック アルゴリズムでも効率的に解決できる特殊なケースに分類されます。
• 現代のコンピュータでは、メモリ キャッシュや並列処理などのハードウェア最適化は、漸近的に最適なアルゴリズムによって「破壊」される可能性があります (分析でこれらのハードウェア最適化が考慮されていないと仮定)。この場合、これらの機能をより有効に活用し、現実的なデータに対して最適なアルゴリズムよりも優れたパフォーマンスを発揮する、最適ではないアルゴリズムが存在する可能性があります。

実際には使用されていない漸近最適アルゴリズムの例としては、単純な多角形の三角測量のためのバーナード・シャゼルの線形時間アルゴリズムがあります。もう 1 つは、「最適な時間と空間でのサイズ変更可能な配列」^{[1]で公開された}サイズ変更可能な配列データ構造です。これは定数時間でインデックスを作成できますが、多くのマシンでは通常の配列インデックス作成に比べて大きな実用上のペナルティを伴います。

正式には、サイズnのインスタンス (入力) に対して、問題を解くのに Ω(f( n )) 時間が必要であることを示す下限定理があるとします( Ω の定義については、 Big O 表記 § Big Omega 表記を参照してください)。この場合、問題を O(f( n )) 時間で解くアルゴリズムは漸近最適であると言われます。これは、限界を使用して表現することもできます。b( n ) が実行時間の下限であり、特定のアルゴリズムに t( n ) の時間がかかるとします。この場合、アルゴリズムが漸近最適であるのは、次の場合です。

${\displaystyle \lim _{n\rightarrow \infty }{\frac {t(n)}{b(n)}}<\infty .}$

この限界が存在する場合、t( n )≥b( n )なので、常に少なくとも1になります。

通常は時間効率に適用されますが、アルゴリズムは漸近的に最適なスペース、ランダム ビット、プロセッサの数、または一般的にビッグ O 表記法を使用して測定されるその他のリソースを使用すると言えます。

あいまいな仮定や暗黙の仮定によって、アルゴリズムが漸近的に最適であるかどうかが不明確になる場合があります。たとえば、下限定理では、比較ソートの場合のように特定の抽象マシンモデルや特定のメモリ構成が想定される場合があります。これらの仮定に違反すると、新しいアルゴリズムは、下限や「漸近的に最適な」アルゴリズムよりも漸近的に優れたパフォーマンスを発揮する可能性があります。

漸近的に最適なアルゴリズムが存在しないことをスピードアップと呼びます。ブルームのスピードアップ定理は、スピードアップを伴う人工的に構築された問題が存在することを示しています。しかし、今日最もよく知られているアルゴリズムの多くが漸近的に最適であるかどうかは未解決の問題です。たとえば、最小全域木 を見つけるアルゴリズムがあります。ここで、 はアッカーマン関数の非常にゆっくりと増加する逆関数ですが、最もよく知られている下限は自明な です。このアルゴリズムが漸近的に最適であるかどうかは不明であり、いずれにせよ解決された場合、重要な成果として歓迎される可能性があります。Coppersmith と Winograd (1982) は、行列乗算が、限られたクラスのアルゴリズム (ラムダ計算によるシュトラッセン型双線形恒等式) の中では弱い形式のスピードアップであることを証明しました。 ${\displaystyle O(n\alpha (n))}$${\displaystyle \alpha (n)}$${\displaystyle \Omega (n)}$

• 要素の一意性の問題
• 漸近的計算複雑性