Competitive analysis (online algorithm) とは

競合分析は、オンラインアルゴリズムの分析(予測不可能な一連の要求を満たす必要があり、未来を見ることができずに各要求を完了しなければならない)のパフォーマンスを、最適なオフラインアルゴリズムのパフォーマンスと比較するオンラインアルゴリズムを分析するために発明された方法です事前に要求のシーケンスを表示することができます。アルゴリズムは、その競合率(その性能とオフラインアルゴリズムの性能との間の比)が限定されている場合、競争的である。従来のワーストケース分析とは異なり、アルゴリズムのパフォーマンスが「ハード」入力のみで測定される場合、競合分析では、「ハード」および「容易」がパフォーマンスによって定義されるハードおよび簡単入力の両方でアルゴリズムがうまく機能することが必要です最適なオフラインアルゴリズムの
多くのアルゴリズムでは、パフォーマンスは入力のサイズだけでなく、その値にも依存します。 1つのそのような例はクイックソートアルゴリズムであり、要素の配列をソートする。このようなデータ依存アルゴリズムは、平均ケースおよび最悪ケースのデータについて分析される。競合分析は、通常はデータに依存するオンラインアルゴリズムとランダム化アルゴリズムのワーストケース分析を行う方法です。
競合分析では、研究対象のアルゴリズムのコストと最適なアルゴリズムの比率を最大にするために、意図的に困難なデータを選択する「敵対者」を想像します。敵は、アルゴリズムの仕組みとその実行中の任意の時点での内部状態を完全に知っている適応的な敵に、敵対するアルゴリズムから無作為に選択されたことについての知識がない、この区別は、ランダム化されたアルゴリズムでのみ意味があることに注意してください。決定論的アルゴリズムの場合、敵対者は、アルゴリズムが将来いつでも必要とする状態を単純に計算し、それに従って適切なデータを選択することができる。
例えば、クイックソートアルゴリズムは、「ピボット」と呼ばれる、平均して、ソートされるデータの中心値からあまり離れていない1つの要素を選択する。クイックソートは、データを2つのファイルに分割します。そのうちの1つは、ピボットの値よりも小さい値を持つすべての要素を含み、もう1つは残りの要素を含みます。クイックソートが何らかの決定論的な方法でピボットを選択した場合(たとえば、リストの最初の要素を常に選択するなど)、敵対者はクイックソートが最悪の場合に実行するように事前にデータを配置するのは簡単です。しかし、クイックソートが何らかのランダム要素をピボットに選ぶと、乱数が何かを知らない敵は、クイックソートの最悪の実行時間を保証するためにデータを並べ替えることができません。
競合分析で最初に分析された古典的オンライン問題(Sleator&Tarjan 1985)は、リストの更新の問題です。アイテムのリストとさまざまなアイテムの要求のシーケンスが与えられれば、リストにアクセスするコストを最小限に抑えますリストの先頭にはアクセスするコストがかかりません。 (通常、アイテムにアクセスするコストはリスト内の位置と同じです。)アクセス後、リストを並べ替えることができます。ほとんどの再編成にはコストがかかります。 Move-To-Frontアルゴリズムは、要求されたアイテムを無制限にアクセスの後で前面に移動させるだけです。 Transposeアルゴリズムは、アクセスしたアイテムをその直前のアイテムと無償で交換します。古典的な分析方法は、転置が特定の状況において最適であることを示した。実際には、Move-To-Frontの方がはるかに優れていました。競合分析は、敵対者が最適なアルゴリズムと比較してTransposeを任意に悪く実行することができることを示すために使用されたが、Move-To-Frontは最適アルゴリズムの2倍以上のコストを負うことはない。
サーバーからのオンライン要求の場合、競合アルゴリズムを使用して将来の不確実性を克服します。つまり、アルゴリズムは未来を「知る」ことはできませんが、虚偽の敵(「競合者」)は「知っています」。同様に、遠隔地で何が起こったかを「知る」ことなく、アルゴリズムが1つの場所に到着する要求に反応しなければならない分散システムの競合アルゴリズムが開発されました。この設定は、(Awerbuch、Kutten&Peleg 1992)に示されている。