Метод дихотомии: различия между версиями

Содержимое удалено Содержимое добавлено
→‎См. также: корректировка урл
Строка 77:
Если говорить на языке чистой математики, метод дихотомии позволяет найти ноль монотонной функции <math>f(x)</math> на отрезке <math>[a;\,b]</math>, если на концах этого отрезка значения функции имеют различные знаки.
 
При этом если требуется точность <math>\varepsilon</math>, то еестьесть если ответ должен отличаться от верного не более чем на <math>\varepsilon</math>, то число вычислений функции будет равно <math>\left\lceil \log_2\frac{b - a}{2 \cdot \varepsilon} \right\rceil + 1</math>. В случае подбора целого числа <math>\varepsilon</math> равно <math>\frac{1}{2}</math> (проверьте).
 
Данная формула справедлива для оптимальной реализации алгоритма. Обычно, программисты пишут так, что на каждом шаге значение функции на одном из концов отрезка вычисляется повторно (одно из значений программа «знала» на предыдущем шаге). И в примере программы, который мы привели ниже, количество вызовов функции (вычислений значения функции) в два раза больше оптимального. На такие «мелочи» промышленные программисты обычно не обращают внимания.