Сложность и измерения

Перед началом: уверенный Go на уровне срезов, мап и циклов — специальных знаний не требуется. Инструменты: Go 1.27, go test -bench. Трудоёмкость: ~4 ч (теория 1.5 ч · практика 2.5 ч).

🔥 Инцидент: «Код не менялся, а поиск стал в тысячу раз медленнее»

Сервис проверки документов работал год. В пятницу дежурный получил алерт: эндпоинт валидации отвечает по 30 секунд. Код не деплоили две недели. Причина — в базе стало 400 000 документов вместо 4 000, а в валидаторе жила проверка дублей «для каждого документа пройтись по всем остальным»: O(n²). На четырёх тысячах это незаметно, на четырёхстах тысячах — в сто раз больше работы и в тридцать раз больше времени ответа. Код был честным линейным циклом — просто вложенным.

📖 Теория

1.1 Big O: язык роста, а не секунд

Big O описывает, как растёт время работы при росте входных данных N. Это прогноз: он не говорит «быстро сейчас», он говорит «что будет, когда данных станет в 10 раз больше».

Три оценки, чтобы не путаться:

• O (верхняя граница) — «растёт не быстрее». Этого достаточно в 95 % разговоров: нам важна гарантия.
• Ω (нижняя граница) — «быстрее не бывает». Любая сортировка сравнениями — Ω(n log n); это не про алгоритм, а про класс задач.
• Θ (точная) — границы совпали: merge sort всегда Θ(n log n), хоть на отсортированном входе, хоть на случайном.

1.2 Пять правил оценки

1. Цикл по N элементам — множитель N.
2. Вложенный цикл по тем же данным — N².
3. Рекурсия, делящая задачу пополам, — log n уровней.
4. Доступ к map/set — O(1) в среднем (и об этом «в среднем» — модуль 4).
5. Константы и младшие слагаемые отбрасываем: O(2n) = O(n), O(n + n²) = O(n²).

Но: отбрасывать константы в оценке — не значит игнорировать их в коде. O(n) с сетевым вызовом внутри цикла проиграет O(n²) со сложением чисел на малых N. O говорит, что будет при росте; что быстрее здесь и сейчас — показывает бенчмарк. Поэтому этот модуль — сразу про оба инструмента.

1.3 Амортизированная стоимость: append — это O(1)

Классический вопрос на собеседовании: если append копирует массив при переполнении, почему его называют O(1)? Потому что копирование случается редко: ёмкость удваивается, и на n добавлений приходится O(n) суммарной работы по перевыделению. В среднем на операцию — константа. Это амортизированный анализ: редкие дорогие операции, размазанные по множеству дешёвых.

Практический вывод: append — O(1) амортизированно, но если размер известен заранее, make([]T, 0, n) убирает сами перевыделения и копии. Модуль 2 покажет это изнутри, а пока — измерим.

1.4 Как измерять в Go

Инструмент — встроенные бенчмарки, никаких внешних библиотек:

go
func BenchmarkDedupQuadratic(b *testing.B) {
    data := generate(10_000) // 10 000 парных значений
    for i := 0; i < b.N; i++ {
        dedupQuadratic(data) // O(n²)
    }
}

func BenchmarkDedupMap(b *testing.B) {
    data := generate(10_000)
    for i := 0; i < b.N; i++ {
        dedupMap(data) // O(n)
    }
}

bash
go test -bench . -benchmem
# BenchmarkDedupQuadratic-8   41   29500000 ns/op        0 B/op   0 allocs/op
# BenchmarkDedupMap-8      14016      85200 ns/op   434176 B/op   8 allocs/op

Как читать вывод:

• ns/op — наносекунды на одну операцию; делите на миллион, чтобы получить миллисекунды, — сравнивайте только порядок.
• allocs/op и B/op — цена по памяти. Быстрая версия может проигрывать по аллокациям: map из первого примера — в 346 раз быстрее, но аллоцирует.
• -count=5 и benchstat — если различия в пределах шума: один запуск бенчмарка ничего не доказывает.

1.5 Компромиссы

Правило: сначала измерить, потом оптимизировать. Оптимизация «по интуиции» — это ставка, а бенчмарк — это данные.

💻 Практика

1. Сравните дубликаты. Реализуйте две функции поиска дублей в []int: квадратичную (двойной цикл) и через map[int]struct{}. Напишите бенчмарки на 1 000 и 10 000 элементов, запустите с -benchmem и запишите оба числа. Ответьте письменно: во сколько раз разошлись версии и на какой размерности квадратичная станет неприемлемой (примите бюджет 100 мс).
2. Измерьте аллокации append. Соберите срез миллиона int двумя способами: append без преаллокации и make([]int, 0, n) + append. Сравните allocs/op и B/op. Объясните разницу, зная амортизированную стоимость из §1.3.
3. Худший случай на практике. Даны две функции поиска в отсортированном срезе: линейная и бинарная (sort.SearchInts). Забенчмарките поиск последнего элемента при n = 10 и n = 100 000. Где линейная ещё конкурентоспособна и почему — что говорит об «отбрасывании констант».

Подсказка по структуре бенчмарк-файла: тестовый файл _test.go в том же пакете, генератор данных — детерминированный (rand.New(rand.NewSource(42))), чтобы замеры повторялись.

🧩 Quiz

✅ Итоги модуля

• Big O — прогноз роста, а не секунды; оценки O/Ω/Θ различаются ролью в рассуждении.
• Амортизированный анализ объясняет, почему append дешёвый, а преаллокация — не микрооптимизация ради красоты.
• Бенчмарк в Go — testing.B + go test -bench -benchmem; читаем ns/op, allocs/op, B/op.
• Сначала измерение, потом оптимизация: интуиция — гипотеза, бенчмарк — доказательство.

🔗 Мостик к Модулю 2

Алгоритмы живут не в вакууме, а в типах Go: срез растёт по ёмкости, строка — это UTF-8, а не массив рун, и копирование спрятано в самых невинных конверсиях. В следующем модуле разберём срезы и строки изнутри — после него бенчмарки из этого модуля будут объяснимы построчно.