計算量の下限
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/23 18:21 UTC 版)
平面内の有限の点の集合の場合、凸多角形として表される凸包を見つける計算複雑性は、還元を使ってソート以上であることが簡単に示せる。数値の集合 x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}} について、 ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})} で表される平面上の点の集合を考える。それらは凸曲線である放物線上にあるため、凸包の頂点が境界に沿って移動すると、番号のソートされた順序が生成されることが簡単にわかる。 x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}} 。明らかに、記述された数値のポイントへの変換と、それらのソートされた順序の抽出には線形時間が必要である。したがって、一般的なケースでは、 凸包はソートよりも速く計算できない。 ソートで標準とされる Ω（n log n）の下限は、決定木モデル内で証明されています。決定木モデルは数値比較のみを実行でき、算術演算は実行できないもので、凸包は算出できない。凸包に適したモデルである代数決定木（英語版）モデルでも、ソートには Ω（n log n）時間が必要であり、このモデルでは凸包にも Ω（n log n）時間が必要である。ただし、たとえば整数のソート（英語版）アルゴリズムを使用して、数値を O（n log n）時間よりも速く並べ替えることができるコンピューター演算のモデルでは、平面凸包もより速く計算できる。例えば、凸包のグラハムスキャン（英語版）アルゴリズムは1回のソートと線形時間の処理で実現される。
※この「計算量の下限」の解説は、「凸包アルゴリズム」の解説の一部です。
「計算量の下限」を含む「凸包アルゴリズム」の記事については、「凸包アルゴリズム」の概要を参照ください。
- 計算量の下限のページへのリンク
