Проверяет понимание логарифмической сложности алгоритмов, ключевой концепции для оценки производительности.
O(log N) — это обозначение логарифмической сложности алгоритма. Оно показывает, что время выполнения алгоритма растет пропорционально логарифму от размера входных данных. В информатике обычно используется логарифм по основанию 2, так как алгоритмы часто делят данные пополам.
Представьте, что у вас есть отсортированный список из 1000 элементов. Линейный поиск (O(N)) в худшем случае потребует 1000 шагов. Бинарный поиск (O(log N)) потребует всего около 10 шагов (log2(1000) ≈ 10). Каждый шаг алгоритм отбрасывает половину данных, что и дает логарифмический рост.
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}O(log N) — это очень эффективная сложность, которую стоит использовать при работе с большими объемами данных, когда требуется быстрый поиск или вставка. Она значительно быстрее линейной (O(N)) и является золотым стандартом для многих алгоритмов.
