最良の出力依存アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/23 18:21 UTC 版)
「凸包アルゴリズム」の記事における「最良の出力依存アルゴリズム」の解説
上記のように、入力サイズ n の凸包を見つける計算量は、Ω（n log n）を下限とする。ただし、一部の凸包アルゴリズムの計算量は、入力サイズ nと出力サイズ h （凸包上の点の数）の両方で決まる。このようなアルゴリズムは、出力依存アルゴリズム（英語版）と呼ばれる。h = o（n）の場合、これらは、Θ（n log n）アルゴリズムよりも漸近的に効率的と考えられる。 出力依存の凸包アルゴリズムの最悪時間計算量の下限は、平面の場合で Ω（n log h）であることが確立された。この最良の時間計算量を達成するアルゴリズムは複数ある。最初のものは、1986年にカークパトリックとサイデルによって発見された（彼らはそれを「究極の凸包アルゴリズム（英語版）」と呼んだ）。1996年には、さらに単純なアルゴリズム、チャンのアルゴリズム（英語版）がチャンによって開発された。
※この「最良の出力依存アルゴリズム」の解説は、「凸包アルゴリズム」の解説の一部です。
「最良の出力依存アルゴリズム」を含む「凸包アルゴリズム」の記事については、「凸包アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「最良の出力依存アルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 最良の出力依存アルゴリズムのページへのリンク
