Делим задачу пополам
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 добавило бы всего один шаг.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
n := 16
steps := 0
for n > 1 {
n = n / 2
steps++
fmt.Println("n теперь", n)
}
fmt.Println("16 стало 1 за", steps, "шага")
}
Бинарный поиск
Бинарный поиск находит значение в отсортированном срезе, каждый раз проверяя средний элемент. Если середина слишком мала, отбрасывается вся левая половина; если слишком велика — правая. Каждая проверка уменьшает диапазон поиска вдвое.
Два маркера, lo и hi, хранят текущий диапазон. Цикл заканчивается, когда значение найдено или диапазон стал пустым.
В Go есть и готовый вариант: slices.BinarySearch() возвращает индекс и логическое значение. Если значения нет, индекс — это позиция, куда его следовало бы вставить.
Бинарный поиск шаг за шагом
В отсортированном срезе из 16 чисел поиск значения 13 требует всего 4 проверок: диапазон сокращается 16 → 8 → 4 → 2 и останавливается на индексе 6. Линейному поиску здесь понадобилось бы 7 шагов — а в худшем случае до 16.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31}
target := 13
steps := 0
lo, hi := 0, len(nums)-1
for lo <= hi {
steps++
mid := (lo + hi) / 2
if nums[mid] == target {
fmt.Println("найдено", target, "по индексу", mid, "за", steps, "проверки")
break
}
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
Бинарный поиск с пакетом slices
slices.BinarySearch() находит 9 по индексу 4. Для отсутствующего значения 10 получаем found == false и индекс 5 — то место, куда нужно вставить 10, чтобы срез остался отсортированным.
Вывод: программа на Go и захваченный вывод
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{1, 3, 5, 7, 9, 11, 13, 15}
i, found := slices.BinarySearch(nums, 9)
fmt.Println("индекс:", i, "найдено:", found)
i, found = slices.BinarySearch(nums, 10)
fmt.Println("индекс:", i, "найдено:", found)
}
O(n log n): сортировка
O(n log n) находится между линейным и квадратичным временем и является сложностью хороших алгоритмов сортировки: данные снова и снова делятся пополам (log n уровней), и на каждом уровне выполняется линейный объём работы (n).
В Go сортировку редко пишут сами — slices.Sort() работает за O(n log n). Один раз отсортировать, а потом много раз применить бинарный поиск — частый и быстрый приём.
Сортировка среза
slices.Sort() упорядочивает 8 чисел примерно за 8 · log 8 = 24 шага — гораздо меньше, чем 64 шага у квадратичной сортировки, и разрыв быстро растёт по мере роста среза.
Вывод: программа на Go и захваченный вывод
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{31, 5, 17, 1, 23, 9, 27, 13}
slices.Sort(nums)
fmt.Println(nums)
}