出力に敏感なアルゴリズム

コンピュータサイエンスにおいて、出力に敏感なアルゴリズムとは、実行時間が入力のサイズではなく、または入力のサイズに加えて、出力のサイズに依存するアルゴリズムのことです。出力サイズが入力のサイズに対して線形から 2 次まで大きく変化する特定の問題では、出力サイズを明示的に考慮した分析によって、同じ漸近的複雑さを持つアルゴリズムを区別する、より適切な実行時間境界を生成できます。

出力に敏感なアルゴリズムの簡単な例として、加算、減算、比較のみを使用して 2 つの正の整数を割った商と余りを計算する 除算アルゴリズム 「減算による除算」が挙げられます。

def  division ( number :  int ,  divisor :  int )  ->  Tuple [ int ,  int ]: 
"""減算による除算。"""除数== 0の場合: ZeroDivisionErrorを発生させます。 number < 1またはdivisor < 1 の場合: ValueErrorを発生させます( f "被除数 ( { number } ) および除数 ( { divisor } )には正の整数のみ。" ) q = 0 r = number while r >= divisor : q += 1 r -= divisor return q , r    
       
         
           
         
            
            
        
      
      
       
          
          
      

出力例:

>>>割り算( 10 ,  2 ) 
(5, 0) 
>>>割り算( 10 ,  3 ) 
(3, 1)

このアルゴリズムはΘ (Q) 時間を要するため、商 Q が小さいことが分かっているシナリオでは高速になります。ただし、Q が大きい場合は、長除算などのより複雑なアルゴリズムの方がパフォーマンスが悪くなります。

平面上の有限の点集合の凸包を求める凸包アルゴリズムでは、 n個の点に対してΩ( n log n ) の時間が必要です。グラハムスキャンのような比較的単純なアルゴリズムでも、この下限に達します。凸包がn 個の点すべてを使用する場合、これが最善の方法です。ただし、多くの実用的な点集合、特にランダムな点集合では、凸包内の点の数hは通常nよりもはるかに小さくなります。その結果、究極の凸包アルゴリズムやChan のアルゴリズムなど、出力に敏感なアルゴリズムでは O( n log h ) 時間しか必要としないため、このような点集合では大幅に高速になります。

出力に敏感なアルゴリズムは計算幾何学アプリケーションで頻繁に登場し、隠れた表面の除去^[1]やルーターテーブルにおける範囲フィルタの競合の解決などの問題で説明されてきました。^[2]

フランク・ニールセンは、グループ化とクエリと呼ばれる出力に敏感なアルゴリズムの一般的なパラダイムを説明し、ボロノイ図のセルを計算するためのアルゴリズムを提供しています。^[3]ニールセンはこれらのアルゴリズムを2つの段階に分割します。出力サイズを推定し、その推定に基づいてデータ構造を構築し、それをクエリして最終的なソリューションを構築します。

出力に敏感なアルゴリズムのより一般的な種類は、問題に対する解の集合を列挙する列挙アルゴリズムです。この文脈では、アルゴリズムのパフォーマンスは、たとえば、任意の 2 つの連続する解の間の遅延を制限するなどのより敏感な測定に加えて、出力に敏感な方法でも測定されます。

• 遅延評価