Назад к вопросам
Senior
12
Какая сложность алгоритма бинарного поиска O?
Компании, где спрашивали
ИП Ганус Александр Андреевич
Ответ от нейросети
sobes.tech AI
Сложность алгоритма бинарного поиска — O(log n).
Объяснение:
- Бинарный поиск работает на отсортированном массиве, каждый раз деля область поиска пополам.
- На каждом шаге количество рассматриваемых элементов уменьшается вдвое.
- Поэтому количество шагов пропорционально логарифму от размера массива.
Пример: если массив из 1 000 000 элементов, бинарный поиск выполнит примерно 20 сравнений (log₂(1 000 000) ≈ 20).