定義
が
を満たすとする。
を与えると
を
の時間計算量で取得できるとして、
を満たす
を
の時間計算量で求めるアルゴリズムが存在する。
アルゴリズム
一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ
上記の記事の後半で紹介しているアルゴリズムを、 で初期化して、
に対して適用すればよい。
実用例
次元平面上に点群があり、ベクトル
の方向に最も遠い点を求めることを考える。
点群の凸包を
、その頂点を順に
として
と定義する。
は
の頂点数を周期とする関数であり、
の極大点が求める点である。