логарифмическое время

EN: logarithmic time

Класс временной сложности O(log n), при котором каждый шаг уменьшает размер оставшейся задачи на постоянный множитель — как правило, вдвое. Бинарный поиск в отсортированном массиве из миллиона элементов требует не более примерно 20 сравнений, так как log₂(1 000 000) ≈ 20.