Сколько стоит решение: время, память и модель вычислений

На десяти заявках повторный просмотр списка почти незаметен. На миллионе заявок он может занять всё время обработки. Измерение секунд полезно, но сначала нужно понять, как число действий связано с количеством входных данных.

Выбираем измеримую операцию

Пусть n — число элементов. Линейный поиск из предыдущей главы в худшем случае делает n сравнений. Поиск каждой из n заявок во всём списке делает до n² сравнений. При n=1000 это тысяча против миллиона, а при n=10000 — десять тысяч против ста миллионов. Увеличение входа в десять раз изменило стоимость решений по-разному.

Мы считаем операции над целыми числами ограниченного размера как постоянные по стоимости. Чтение файла целиком, сравнение длинных строк или сложение произвольно длинных чисел этим договором не покрываются. Если ключ имеет длину m, сравнение ключей может потребовать O(m) работы. В оценке нужно называть, что считаем входом.

Что означает Big O

Запись O(n) задаёт асимптотическую верхнюю границу с точностью до постоянного множителя для достаточно большого n. Она не обещает n наносекунд. Θ(n) говорит о совпадающих верхней и нижней границах порядка роста, а Ω(n) — о нижней границе. Можно формально назвать линейный алгоритм O(n²), но это слишком грубая оценка для сравнения решений.

Различайте худший случай, средний по явно выбранному распределению и амортизированный. Амортизированная оценка распределяет суммарную стоимость серии операций между ними. Она не требует случайного входа. Средняя оценка без объяснения распределения часто скрывает неподтверждённое предположение.

Считаем циклы

comparisons := 0
for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ {
        comparisons++
    }
}

Число итераций равно (n−1)+(n−2)+...+1 = n(n−1)/2. Для n=4 ответ 6, для n=1000 — 499500. Два вложенных цикла не всегда дают квадрат: если внутренний указатель за весь внешний цикл продвигается только n раз, суммарная работа может быть линейной. Это понадобится в скользящем окне.

В последовательных фазах стоимости складываются: O(n)+O(n log n) даёт O(n log n). В независимых размерах сохраняйте обе переменные: просмотр всех пар пользователей и событий имеет O(u·e), а не обязательно O(n²).

Память тоже имеет цену

Срез из n целых значений занимает O(n) памяти. Пара счётчиков — O(1). Рекурсивный вызов использует стек, который нельзя забывать. Возвращённый массив тоже занимает место: отдельно назовите память результата и дополнительную рабочую память. Фраза «O(1), если не считать всё важное» не помогает оценить ресурс.

Динамический массив иногда перераспределяет хранилище и копирует элементы. Геометрическое увеличение ёмкости даёт амортизированное O(1) добавление в учебной модели. Точные правила роста append в Go относятся к реализации; нельзя опираться на обещание строго удваивать capacity. Измерьте len и cap, но не делайте договор программы зависимым от конкретной последовательности capacity.

Практика и измерение

Создайте функции подсчёта сравнений для линейного поиска без совпадения и для всех пар. В тесте проверьте n=0,1,4. Затем выведите числа для n=100,1000,10000. Не выполняйте квадратичный цикл на миллиарде элементов ради демонстрации: математическое выражение уже показывает масштаб.

Для измерения реального кода используйте go test -bench . -benchmem. Подготовку входа вынесите из измеряемого участка. Убедитесь, что результат используется, а многократный запуск не меняет данные так, что второй проход решает другую задачу. Нельзя сравнивать два алгоритма на разных распределениях и объяснять разницу только Big O.

Критерии готовности: сформулирован худший случай; показаны число действий и размер памяти; различаются стоимость одной операции и серии; измерение не объявлено доказательством асимптотики. Практика — 35 минут.

Разбор

Пустой вход даёт ноль сравнений обоим счётчикам. Число пар на четырёх элементах — шесть. Если линейный поиск завершился на первом элементе, это лучший случай, а не опровержение худшей оценки O(n). Двоичный поиск далее будет делить диапазон пополам, поэтому число итераций связано с логарифмом размера.

Источники: Princeton: анализ алгоритмов, Go: тестирование и benchmarks, спецификация срезов Go.