Модуль: Алгоритмы · Уровень: Middle+/Senior

TL;DR#

• Big-O описывает асимптотический рост ресурсов (время/память) при росте входа n, отбрасывая константы и младшие члены.
• Оцениваем отдельно время и память — оптимизация одного часто ухудшает другое (trade-off).
• Амортизированная сложность — средняя стоимость операции на длинной серии (классика: append к слайсу = O(1) амортизированно).
• В Go важно знать: append может реаллоцировать и копировать (амортизированно O(1)), доступ к map — O(1) в среднем, сортировка sort.Slice — O(n log n).
• На senior ждут не «знаю определение», а умения вывести сложность по коду, заметить скрытые копирования и аллокации, обсудить worst/average/best case.

Теория#

Что такое Big-O формально#

O(f(n)) — множество функций, ограниченных сверху c·f(n) начиная с некоторого n₀. На практике: «как растёт ресурс при стремлении n к бесконечности».

Семейство нотаций:

• O (Big-O) — верхняя граница (worst case или просто «не хуже чем»).
• Ω (Omega) — нижняя граница (не лучше чем).
• Θ (Theta) — точная граница (и сверху, и снизу).

На интервью обычно говорят «O», подразумевая Θ для worst case. Будьте готовы уточнить, о каком случае идёт речь.

Иерархия сложностей (от лучшей к худшей)#

Ориентир по n для лимита ~1 сек (~10⁸ операций):

• n ≤ 10–12 → допустим O(n!), O(2ⁿ)
• n ≤ 20–25 → O(2ⁿ)
• n ≤ 500 → O(n³)
• n ≤ 10⁴ → O(n²)
• n ≤ 10⁶ → O(n log n)
• n ≤ 10⁸ → O(n)

Как оценивать сложность по коду#

1. Последовательные блоки складываются → берём максимум: O(n) + O(n log n) = O(n log n).
2. Вложенные циклы перемножаются: цикл по n внутри цикла по n → O(n²).
3. Рекурсия — через рекуррентное соотношение и Master Theorem.

Master Theorem для T(n) = a·T(n/b) + f(n):

• merge sort: T(n) = 2T(n/2) + O(n) → O(n log n)
• бинарный поиск: T(n) = T(n/2) + O(1) → O(log n)

// O(n²): для каждого элемента — проход по остатку
func hasDuplicateNaive(a []int) bool {
    for i := 0; i < len(a); i++ {
        for j := i + 1; j < len(a); j++ {
            if a[i] == a[j] {
                return true
            }
        }
    }
    return false
}

// O(n) время, O(n) память: размен памяти на скорость
func hasDuplicate(a []int) bool {
    seen := make(map[int]struct{}, len(a)) // pre-size — меньше реаллокаций
    for _, v := range a {
        if _, ok := seen[v]; ok {
            return true
        }
        seen[v] = struct{}{}
    }
    return false
}

Время vs Память (trade-off)#

Часто можно ускорить алгоритм ценой памяти (мемоизация, хеш-таблицы) или сэкономить память ценой времени (in-place, пересчёт). На интервью проговаривайте обе оси — это признак зрелости.

Пример: подсчёт сложности по памяти учитывает только дополнительную память (auxiliary space), не вход. In-place сортировка слайса — O(1) доп. памяти (хотя sort.Slice использует стек рекурсии O(log n)).

Амортизированная сложность#

Усреднённая стоимость операции по длинной последовательности, даже если отдельные операции дорогие. Не то же самое, что average-case (там усредняем по входам, тут — по времени серии).

Классика — append: слайс при переполнении capacity реаллоцирует новый массив (обычно ×2 для малых, ×1.25 для больших) и копирует элементы. Один append иногда O(n), но суммарно n аппендов = O(n), то есть O(1) амортизированно. Метод анализа — банковский (накапливаем «кредит» на дешёвых операциях).

s := make([]int, 0)        // cap=0
for i := 0; i < 1000; i++ {
    s = append(s, i)       // изредка реаллокация+копирование, в среднем O(1)
}
// Если знаем размер заранее — убираем реаллокации:
s2 := make([]int, 0, 1000) // cap=1000, ни одной реаллокации

Типичные сложности операций в Go#

Slice []T:

Map map[K]V:

Map не даёт гарантий worst-case O(1) (в отличие от сбалансированного дерева O(log n)), но на практике коллизии редки.

Прочее stdlib:

Подводные камни / gotchas#

• Slicing разделяет backing array. b := a[1:3] не копирует — изменение b[0] меняет a[1], а append(b, x) может затереть данные a. Память исходного массива не освобождается, пока жив хоть один под-слайс (утечка). Лекарство: slices.Clone или append([]T(nil), src...).
• Скрытое O(n²): конкатенация строк через += в цикле, append в начало через пересоздание, удаление элементов сдвигом в цикле.
• Pre-sizing make(map, n) / make([]T, 0, n) — не меняет Big-O, но убирает реаллокации/рехеши; на интервью это плюс к «понимаю аллокации».
• Map worst case O(n) — теоретически возможна деградация; для гарантий нужен сбалансированный поиск. Редко спрашивают, но senior должен знать.
• Константы важны на практике: O(n) с тяжёлой константой может быть медленнее O(n log n) на реальных n. Big-O — про асимптотику, не про конкретный бенч.
• Память рекурсии — глубина стека входит в space complexity. Глубокая рекурсия = O(глубины) памяти + риск переполнения стека.
• delete из map не уменьшает память — занятые бакеты остаются. Для освобождения — пересоздать map.

Вопросы / задачи на собеседовании#

В: Какова сложность append к слайсу и почему? О: O(1) амортизированно. Отдельный append может вызвать реаллокацию (новый массив + копирование = O(n)), но рост capacity геометрический (×2 / ×1.25), поэтому суммарная стоимость n аппендов — O(n), то есть O(1) на операцию. Если cap известен заранее, можно избежать реаллокаций через make([]T, 0, n).

В: Чем амортизированная сложность отличается от average-case? О: Average-case усредняет по распределению входов (одна операция, разные данные). Амортизированная — усредняет стоимость по длинной серии операций на одной структуре, гарантируя среднюю стоимость даже при детерминированном worst-case входе. Append — амортизированно O(1) независимо от данных.

В: Сложность map lookup в Go? О: O(1) в среднем, O(n) в худшем случае (все ключи в один бакет / много коллизий). Go использует хеш-таблицу с бакетами; на практике коллизии редки, но формальной гарантии O(1) worst-case нет.

В: Дан код с двумя последовательными циклами по n и одним вложенным двойным. Итоговая сложность? О: O(n) + O(n) + O(n²) = O(n²). Последовательные блоки складываются, берём максимум; младшие члены отбрасываются.

В: Почему b := a[i:j] это O(1), и в чём опасность? О: Слайсинг создаёт новый header (ptr, len, cap), указывающий в тот же backing array — копирования нет. Опасность: разделяемая память (мутации видны обоим), удержание всего большого массива из-за маленького под-слайса (утечка), и затирание данных при append, если есть свободный cap. Решение — slices.Clone.

В: Как оценить сложность рекурсивной функции? О: Составить рекуррентное соотношение T(n) и решить — подстановкой, деревом рекурсии или Master Theorem для вида a·T(n/b)+f(n). Пример: merge sort 2T(n/2)+O(n) = O(n log n); наивный fib T(n-1)+T(n-2) = O(2ⁿ).

В: Алгоритм A — O(n log n), B — O(n). Какой выбрать? О: Асимптотически B лучше, но надо смотреть константы, паттерн доступа к памяти (cache locality), доп. память B (часто O(n) hash vs in-place sort), стабильность и реальный диапазон n. На малых/средних n O(n log n) sort может выиграть у hash-подхода из-за константы и локальности. Ответ «зависит» с обоснованием ценнее, чем «B».

На что копают на senior+#

• Умение вывести сложность из кода, а не процитировать таблицу; заметить скрытое квадратичное поведение (строки, вставки).
• Различение time vs space и обсуждение trade-off осознанно.
• Понимание аллокаций в Go: реаллокации слайсов, рехеши map, escape analysis (попадает ли переменная в heap), влияние GC.
• Worst/average/amortized — чёткое разграничение, особенно для map и append.
• Practical vs theoretical: знание, что константы и cache locality решают на реальных данных, и умение это измерить (testing.B, pprof).
• Анализ сложности параллельных решений (work/depth), если зашла речь о горутинах.