Делим задачу пополам
O(log n) означает логарифмическое время: каждый шаг сокращает оставшуюся работу вдвое. Поскольку деление пополам уменьшает числа очень быстро, удвоение входных данных добавляет всего один дополнительный шаг.
Для 16 элементов нужно 4 деления пополам, для 32 элементов — 5, для миллиона — около 20, для миллиарда — около 30. Именно поэтому логарифмические алгоритмы кажутся мгновенными даже на огромных данных.
Классический пример — бинарный поиск, но он работает только на отсортированных данных. Чтобы делить пополам, нужен порядок, иначе не понять, какую половину отбросить.
Цикл с делением пополам
Проще всего увидеть O(log n) на цикле, который делит n на 2, пока не дойдёт до 1. Количество повторений — это логарифм n: при n = 16 цикл выполняется 4 раза, потому что 2 · 2 · 2 · 2 = 16.
Делим пополам, пока не останется единица
16 превращается в 8, 4, 2, 1 — четыре шага. Удвоение n до 32 добавило бы всего один шаг.
Вывод: программа на TypeScript и захваченный вывод
let n = 16
let steps = 0
while (n > 1) {
n = Math.floor(n / 2)
steps++
console.log("теперь n равно", n)
}
console.log("16 превратилось в 1 за", steps, "шагов")
Бинарный поиск
Бинарный поиск находит значение в отсортированном массиве, всегда проверяя средний элемент. Если середина слишком мала, отбрасывается вся левая половина; если слишком велика — правая. Каждая проверка уменьшает диапазон поиска вдвое.
Два маркера, lo и hi, задают текущий диапазон. Цикл заканчивается, когда значение найдено или диапазон пуст.
В TypeScript нет собственного бинарного поиска. Встроенные способы поиска — indexOf() и includes() — проходят массив с начала, поэтому остаются O(n) даже тогда, когда данные уже отсортированы. На отсортированных данных написанный вручную цикл работает быстрее.
Бинарный поиск шаг за шагом
В отсортированном массиве из 16 чисел поиск значения 13 требует всего 4 проверок: диапазон сокращается 16 → 8 → 4 → 2 и приводит к индексу 6. Линейному поиску здесь понадобилось бы 7 шагов — а могло бы и все 16.
Вывод: программа на TypeScript и захваченный вывод
const nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
const target = 13
let steps = 0
let lo = 0
let hi = nums.length - 1
while (lo <= hi) {
steps++
const mid = Math.floor((lo + hi) / 2)
if (nums[mid] === target) {
console.log("найдено", target, "по индексу", mid, "после", steps, "проверок")
break
}
if (nums[mid] < target) {
lo = mid + 1
} else {
hi = mid - 1
}
}
Встроенный поиск всё равно линейный
Оба способа поиска согласны: 9 находится по индексу 4. Но indexOf() добирается туда, проверив 5 элементов, а бинарному поиску нужно 3 проверки. Для отсутствующего значения 10 indexOf() проверяет все 8 элементов и возвращает -1; бинарный поиск останавливается после 3 проверок и даже может сообщить индекс 5 — место, куда следовало бы вставить 10, чтобы массив остался отсортированным.
На 8 элементах разница невелика. На миллионе это примерно 1 000 000 шагов против 20.
Вывод: программа на TypeScript и захваченный вывод
const nums = [1, 3, 5, 7, 9, 11, 13, 15]
// Сколько элементов приходится затронуть встроенному проходу: он идёт с начала.
function scanned(xs: number[], target: number): number {
let steps = 0
xs.findIndex((x) => {
steps++
return x === target
})
return steps
}
interface Found {
index: number
checks: number
insertAt: number
}
// Написанный вручную бинарный поиск: каждая проверка уменьшает диапазон вдвое.
function binarySearch(xs: number[], target: number): Found {
let lo = 0
let hi = xs.length - 1
let checks = 0
while (lo <= hi) {
checks++
const mid = Math.floor((lo + hi) / 2)
if (xs[mid] === target) {
return { index: mid, checks, insertAt: mid }
}
if (xs[mid] < target) {
lo = mid + 1
} else {
hi = mid - 1
}
}
return { index: -1, checks, insertAt: lo }
}
for (const target of [9, 10]) {
console.log("искомое значение", target)
console.log(" indexOf:", nums.indexOf(target), "includes:", nums.includes(target),
"- просмотрено", scanned(nums, target), "из", nums.length, "элементов")
const hit = binarySearch(nums, target)
if (hit.index >= 0) {
console.log(" бинарный поиск: индекс", hit.index, "после", hit.checks, "проверок")
} else {
console.log(" бинарный поиск: не найдено после", hit.checks, "проверок -",
target, "было бы вставлено по индексу", hit.insertAt)
}
}
O(n log n): сортировка
O(n log n) находится между линейной и квадратичной сложностью и является сложностью хороших алгоритмов сортировки: данные снова и снова делятся пополам (log n уровней), и на каждом уровне выполняется линейный объём работы (n).
Сортировку редко пишут самостоятельно — у каждого массива уже есть sort(), и это O(n log n). Отсортировать один раз, а затем много раз применять бинарный поиск — распространённый и быстрый приём.
Сортировка массива
nums.sort((a, b) => a - b) упорядочивает 8 чисел примерно за 8 · log 8 = 24 шагов — намного меньше, чем 64 шага квадратичной сортировки, и разрыв быстро растёт с увеличением массива.
Компаратор здесь не необязателен. Без него sort() сравнивает значения как текст: "13" начинается с 1, поэтому оказывается перед "5". Программа выводит оба порядка.
Вывод: программа на TypeScript и захваченный вывод
const nums = [31, 5, 17, 1, 23, 9, 27, 13]
const show = (xs: number[]): string => `[ ${xs.join(", ")} ]`
// Без компаратора sort() сравнивает значения как текст.
console.log("как текст:", show([...nums].sort()))
// С числовым компаратором порядок такой, какой нам нужен.
console.log("как числа:", show([...nums].sort((a, b) => a - b)))