漸近的に最適なアルゴリズム

コンピュータサイエンスにおいて、アルゴリズムが漸近的に最適であるとは、大まかに言えば、大きな入力に対して、考えられるあらゆるアルゴリズムよりも最悪の場合でも定数倍（入力サイズに依存しない）だけ性能が劣る場合を指します。これは、ビッグオー記法が広く用いられていることから、コンピュータサイエンスの研究においてよく見られる用語です。

より厳密に言えば、アルゴリズムが特定の資源に関して漸近的に最適であるとは、その問題がΩ( f ( n ))の資源を必要とすることが証明されており、かつアルゴリズムがO ( f ( n ))しか使用しないことが証明されている場合である。

これらの証明には、特定の計算モデル、すなわち入力データに対して許容される演算に関する一定の制約を前提とする必要がある。

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

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

アルゴリズムが漸近的に最適であることの帰結として、入力が十分に大きい場合、どのアルゴリズムも定数倍以上の差でそれを上回ることはできない。このため、漸近的に最適なアルゴリズムは、研究における「到達点」、つまり劇的に改善できない結果の達成とみなされることが多い。逆に、アルゴリズムが漸近的に最適でない場合、入力のサイズが大きくなるにつれて、そのアルゴリズムは最良のアルゴリズムよりも性能が著しく低下することを意味する。

実際には、漸近的な優位性を持たない場合でも、より優れたパフォーマンスを発揮するアルゴリズムを見つけることが有用です。新しいアルゴリズムは、特定の入力に対するパフォーマンスの向上、他のリソースの使用量の削減、記述や実装の簡素化といった利点ももたらす可能性があります。したがって、漸近的に最適なアルゴリズムが常に「最終目標」となるわけではありません。

漸近的に最適なアルゴリズムは重要な理論的成果ではあるものの、多くの実際的な状況では必ずしも使用されるとは限らない。

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

実際に使用されていない漸近的に最適なアルゴリズムの例として、ベルナール・シャゼルの単純多角形の三角分割のための線形時間アルゴリズムが挙げられます。もう1つは、「最適な時間と空間でのサイズ変更可能な配列」^{[ 1 ]}で発表されたサイズ変更可能な配列データ構造で、定数時間でインデックス付けできますが、多くのマシンでは通常の配列インデックス付けに比べて実用上大きなペナルティが発生します。

形式的には、ある問題がサイズnのインスタンス (入力) に対してΩ( f ( n )) の時間で解けることを示す下限定理があると仮定します (Ω の定義については、ビッグ O 記法 §ビッグ オメガ記法を参照)。このとき、問題をO ( f ( n )) 時間で解くアルゴリズムは、漸近的に最適であると言われます。 

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

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

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

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