Изменения

'''Поиск с помощью золотого сечения''' (''Golden section search'') - это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащий служащего для поиска нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выигрыш в производительности.

На Так как на каждой итерации исследуемый отрезок сокращается мы считаем два значения функции и уменьшаем область поиска в <tex>\varphi</tex> раз и делается один расчет функции. Делается это до тех порполтора раза, пока не станет <tex>|L| < r - l > \varepsilon</tex>. Если считать, что одна итерация выполняется за 1 времени, то потребуется <tex> n </tex> операций, чтобы: время работы алгоритма составит <tex>L 2 \cdot (\frac{1}log_{\varphifrac32})^n < \varepsilon \Rightarrow n = [log_{\varphi}left(\frac{Lr - l}{\varepsilon}\right)]</tex>.

ЗначитТак как на каждой итерации мы считаем одно значение функции и уменьшаем область поиска в <tex> \varphi </tex> раз, пока <tex> r - l > \varepsilon</tex>,то время работы можно оценивать как алгоритма составит <tex> log_{\varphi}(\frac{Lr - l}{\varepsilon})</tex>. Если удельный вес вычисления функции <tex> f </tex> достаточно большой, тогда получим ускорение работы примерно в 2,3 4 раз по сравнению с неулучшенным [[Троичный поиск|троичным поиском]].