定義 が を満たすとする。 を与えると を の時間計算量で取得できるとして、 を満たす を の時間計算量で求めるアルゴリズムが存在する。 アルゴリズム 一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ 上記の記事の後半で紹介してい…

概要 三分探索を行うと極小点が つも求まらないような数列を構成した。 また、一般の数列に対して の時間計算量で極小点を つ求めるアルゴリズムを説明する。 定義 を実数列とする。 整数 が の極小点であることを、 を満たすことと定義する。 ただし仮想的…