272
правки
Изменения
Нет описания правки
=== Время работы ===
При условии, что значения элементов близки к арифметической прогрессии, за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>.<br/>Поэтому среднее время работы алгоритма: <tex> O(\log \log n) </tex>.<br/>
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
