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