Формально g(n) = O(f(n)), если существуют c > 0 и n₀ такие, что g(n) ≤ c·f(n) при всех n ≥ n₀. То есть O читается как «не хуже, чем», Ω как «не лучше, чем», Θ как «ровно такого порядка». На собесе почти всегда говорят «O», подразумевая Θ; проговорить разницу одной фразой уже плюс.

Пространственная сложность

Считается дополнительная (auxiliary) память, то есть всё, что алгоритм выделяет сверх входных данных. Про что забывают: глубина рекурсии (каждый кадр стека занимает память), мапы для мемоизации, промежуточные слайсы от append, копия строки при []rune(s). Фраза «решение in-place, O(1) дополнительной памяти» сразу показывает, что ты понимаешь разницу.

Как это звучит на собесе

func twoSum(nums []int, target int) (int, int) {
    seen := make(map[int]int, len(nums))
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return j, i
        }
        seen[v] = i
    }
    return -1, -1
}
// twoSum([]int{2, 7, 11, 15}, 9) → 0, 1
// twoSum([]int{1, 2}, 100)       → -1, -1

«n здесь длина nums. Один проход, внутри одна проверка мапы и одна запись, обе амортизированно O(1). Итого O(n) по времени. По памяти мапа, в худшем случае на все n элементов, то есть O(n). Худший случай по времени формально O(n²), если все ключи дадут коллизии, но в Go хеш рандомизирован сидом, так что практически это O(n).»

Шкала, которую надо чувствовать

Слайс устроен как заголовок из трёх слов (ptr, len, cap) над непрерывным массивом. Отсюда всё поведение:

Что такое амортизация

Амортизированная сложность означает среднюю стоимость операции в длинной серии, а не среднее по случайным входам. Когда cap исчерпан, growslice выделяет новый массив (примерно вдвое больше для небольших слайсов, с плавным коэффициентом, стремящимся к 1.25, после 256 элементов) и копирует туда всё, а это O(n). Но такое случается тем реже, чем больше слайс: суммарное копирование при n вставках складывается в геометрическую прогрессию n + n/2 + n/4 + … < 2n, то есть O(n) на всю серию, O(1) на операцию.

Откуда берётся O(1)

Хеш-функция раскидывает ключи по бакетам примерно равномерно, а load factor (в старой мапе 6.5 элементов на бакет из 8 слотов) ограничивает длину линейного поиска внутри бакета константой. При превышении фактора таблица удваивается, и данные переезжают инкрементально, по паре бакетов на каждую запись или удаление, чтобы не было длинной паузы. В Go 1.24 мапу переписали на Swiss Tables: группа из 8 слотов с байтами-метаданными, которые сканируются одним махом: на amd64 это SIMD-инструкция, на остальных - трюк с 64-битным словом. Асимптотика та же, константа и память лучше.

Откуда берётся O(n)

• Патологические коллизии. Если все ключи дают один и тот же бакет, поиск вырождается в перебор. В Go это нельзя вызвать снаружи: каждая мапа при создании получает случайный seed, поэтому одна и та же последовательность ключей на разных запусках раскладывается по-разному, и это защита от HashDoS.
• Плохой хеш у своего типа ключа. Только для языков, где хеш пишет пользователь. В Go хеш для comparable-типов генерирует компилятор, так что испортить его ты не можешь, зато можешь выбрать тяжёлый ключ (длинная строка, большая структура).

Скрытые расходы, о которых стоит сказать

m := map[string]int{}
m[longKey] = 1   // хеш считается по всем байтам ключа: O(len(key))
                 // при коллизии ещё и побайтовое сравнение строк

// Мапу нельзя обойти в порядке ключей: порядок итерации намеренно рандомизирован
for k := range m { ... }   // порядок каждый раз другой

// Отсортированный обход стоит O(n log n):
keys := slices.Sorted(maps.Keys(m))   // Go 1.23: итератор + сортировка

Почему на практике список проигрывает

• Кэш. Процессор читает память линиями по 64 байта и умеет предсказывать последовательный доступ. Слайс из int даёт 8 значений на линию и работающий префетч. Список прыгает по случайному адресу на каждом шаге, префетч бесполезен. На обходе это 10–50× при одинаковой O(n).
• Аллокации и GC. Миллион узлов даёт миллион объектов, которые GC обязан просканировать (они содержат указатели). Слайс из миллиона int остаётся одним объектом, и для []int GC вообще не сканирует содержимое, потому что в типе нет указателей.
• Оверхед. container/list хранит значения в any, добавляя боксинг и косвенность.

Когда список всё-таки нужен

• LRU-кэш: мапа даёт узел за O(1), список переставляет его в голову за O(1). Слайсом так не сделать, мешает сдвиг O(n).
• Очередь задач с удалением из середины по хендлу (например, планировщик таймеров).
• Структуры, где нельзя инвалидировать указатели на элементы при росте: у слайса append может переселить массив, и все &s[i] станут указывать на старую память.

Стек

stack := []int{}
stack = append(stack, v)             // push
top := stack[len(stack)-1]           // peek
stack = stack[:len(stack)-1]         // pop
// если T содержит указатели, обнули слот перед укорачиванием:
// stack[len(stack)-1] = nil

Очередь: почему наивный вариант плох

q = q[1:] двигает вперёд ptr и уменьшает len, но массив под слайсом остаётся живым целиком, пока жив хоть один слайс на него. В цикле enqueue/dequeue underlying array растёт монотонно: обработали миллион задач - держим память под миллион, хотя в очереди три элемента. Формально это не «утечка» (память достижима), но ведёт себя именно так.

Кольцевой буфер

Храним массив фиксированного размера плюс head и size. Хвост вычисляется как (head + size) % cap, поэтому индексы «заворачиваются» через ноль и память переиспользуется. Все четыре операции стоят O(1), рост амортизированно O(1).

type Queue[T any] struct {
    buf        []T
    head, size int
}

func (q *Queue[T]) Push(v T) {
    if q.size == len(q.buf) {
        q.grow()
    }
    q.buf[(q.head+q.size)%len(q.buf)] = v
    q.size++
}

func (q *Queue[T]) Pop() (T, bool) {
    var zero T
    if q.size == 0 {
        return zero, false
    }
    v := q.buf[q.head]
    q.buf[q.head] = zero                 // иначе буфер держит объект
    q.head = (q.head + 1) % len(q.buf)
    q.size--
    return v, true
}
// var q Queue[string]   (grow такой же, как у Deque выше)
// q.Push("a"); q.Push("b"); q.Push("c")
// Pop подряд: "a" "b" "c", затем ("", false)

BST

Инвариант: в левом поддереве ключи меньше корня, в правом больше. Поиск, вставка и удаление стоят O(h). Проблема в том, что h зависит от порядка вставки: если добавлять уже отсортированные данные (тот самый автоинкрементный ID), каждое новое значение уходит вправо, и дерево становится связным списком с O(n) на всё.

Лечат это самобалансирующиеся деревья: AVL (разница высот поддеревьев не больше 1; строже балансирует, значит быстрее читает, но больше поворотов при записи) и красно-чёрное (слабее балансирует, зато дешевле вставка; на нём построены std::map в C++ и TreeMap в Java). В стандартной библиотеке Go сбалансированного дерева нет, есть мапа и sort.

Почему B-tree в базах

• Читается всегда целая страница. СУБД читает диск и держит в буферном кэше страницы по 8–16 КБ. Читать один узел BST с двумя указателями - значит потратить целое чтение страницы ради пары байт.
• Коэффициент ветвления. В страницу 8 КБ влезают сотни ключей, поэтому у B-tree ветвление ~100–500, а высота на миллиард строк всего 3–4. У BST на том же объёме log₂ 10⁹ ≈ 30. Получается 30 обращений против 4.
• B+tree и range scan. В B+tree данные лежат только в листьях, а листья связаны в двусвязный список. Поэтому WHERE x BETWEEN a AND b сводится к одному спуску и последовательному проходу по листьям, а ORDER BY по индексу вообще не требует сортировки.
• Заполнение страниц и fillfactor. B-tree держит узлы заполненными минимум наполовину, что ограничивает фрагментацию и число расщеплений.

Устройство

Каждый узел хранит переходы по символам и флаг «здесь заканчивается слово». Слова с общим префиксом делят один и тот же путь: «go», «gopher», «gorm» идут по общей ветке g → o и расходятся дальше. Ключ не хранится целиком нигде, он «размазан» по рёбрам.

Где применяют

• Поисковые подсказки / автодополнение. Спуск по введённому префиксу за O(L), затем обход поддерева. Часто в узлах ещё хранят топ-k популярных продолжений, чтобы не обходить поддерево целиком.
• Роутинг HTTP. httprouter и chi держат сжатый trie (radix tree) и разбирают пути вида /users/:id/orders за один проход по URL, без регулярок.
• IP-маршрутизация (longest prefix match), словари T9, проверка орфографии, поиск запрещённых слов (Aho–Corasick это trie плюс суффиксные ссылки).

Главная проблема и её решение

Наивный trie расходует память дико: на каждое слово почти столько узлов, сколько в нём символов, а в каждом узле сидит мапа или массив на весь алфавит. Отсюда radix tree (он же patricia): цепочки узлов с одним ребёнком склеиваются в один узел с целой подстрокой на ребре. Для URL-роутера или IP-таблицы это сокращает число узлов на порядок.

Механика

• Push: положить в конец массива и «всплывать» (sift up), меняясь местами с родителем, пока нарушается инвариант. Максимум log n обменов.
• Pop: минимум лежит в a[0]. Забираем его, переносим последний элемент в корень, сокращаем длину и «топим» (sift down), меняясь с меньшим из детей.
• Init: sift down для всех узлов с n/2 - 1 вниз до 0. Это O(n), а не O(n log n): у большинства узлов маленькая высота, и сумма высот всех узлов линейна.
• Fix(i): элемент изменился, восстанавливаем инвариант из позиции i за O(log n). Именно так делают «изменить приоритет» в очереди с приоритетами.

container/heap: пакет даёт алгоритмы, хранилище - твоё

// Очередь с приоритетами по задачам
type Item struct {
    Value    string
    Priority int
    index    int   // позиция в куче, нужна для heap.Fix / heap.Remove
}

type PQ []*Item

func (pq PQ) Len() int { return len(pq) }
// Больший Priority = выше приоритет → max-heap: знак ">"
func (pq PQ) Less(i, j int) bool { return pq[i].Priority > pq[j].Priority }
func (pq PQ) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index, pq[j].index = i, j     // синхронизируем index
}

func (pq *PQ) Push(x any) {
    it := x.(*Item)
    it.index = len(*pq)
    *pq = append(*pq, it)
}

func (pq *PQ) Pop() any {
    old := *pq
    n := len(old)
    it := old[n-1]
    old[n-1] = nil      // помогаем GC
    it.index = -1
    *pq = old[:n-1]
    return it
}

func main() {
    pq := &PQ{}
    heap.Init(pq)
    heap.Push(pq, &Item{Value: "low", Priority: 1})
    heap.Push(pq, &Item{Value: "high", Priority: 9})

    top := (*pq)[0]                 // максимум за O(1), без извлечения
    top.Priority = 0
    heap.Fix(pq, top.index)         // приоритет изменился, чиним за O(log n)

    it := heap.Pop(pq).(*Item)      // O(log n)
    _ = it
}

Представление

// Список смежности берут почти всегда
type Graph map[int][]int
// или, если вершины плотно занумерованы 0..V-1, быстрее и компактнее:
adj := make([][]int, V)
adj[u] = append(adj[u], v)

// Матрица смежности нужна на плотных графах с частыми проверками "есть ребро?"
m := make([][]bool, V)
for i := range m { m[i] = make([]bool, V) }
m[u][v] = true

Реальные графы (соцсеть, дорожная сеть, зависимости сервисов) разрежены: E ≪ V². Матрица на 10⁵ вершин займёт 10¹⁰ ячеек, то есть неприменима. Поэтому по умолчанию список.

BFS: очередь, уровни, кратчайший путь

// Кратчайший путь в невзвешенном графе + восстановление маршрута
func ShortestPath(g Graph, from, to int) []int {
    if from == to {
        return []int{from}
    }
    prev := map[int]int{from: -1}
    queue := []int{from}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        for _, v := range g[u] {
            if _, seen := prev[v]; seen {
                continue
            }
            prev[v] = u                 // помечаем при добавлении, иначе дубли в очереди
            if v == to {
                // разворачиваем путь назад по prev
                path := []int{to}
                for x := u; x != -1; x = prev[x] {
                    path = append(path, x)
                }
                slices.Reverse(path)
                return path
            }
            queue = append(queue, v)
        }
    }
    return nil
}
// g := Graph{1: {2, 3}, 2: {4}, 3: {4, 5}, 4: {5}, 5: nil}
// ShortestPath(g, 1, 5) → [1 3 5]   - два ребра, а не три через 2→4→5
// ShortestPath(g, 1, 1) → [1]
// ShortestPath(g, 5, 1) → [] (nil)  - граф ориентированный, пути назад нет

Обход «по уровням» (сколько шагов до вершины) получается, если замерить длину очереди в начале итерации: levelSize := len(queue), и сделать ровно столько извлечений. Тот же приём, что и в задаче «BFS по уровням дерева».

DFS: рекурсия или явный стек

// Поиск цикла в ориентированном графе: три цвета
const (white = 0; grey = 1; black = 2)

func hasCycle(g Graph, V int) bool {
    color := make([]int, V)
    var dfs func(u int) bool
    dfs = func(u int) bool {
        color[u] = grey                 // вошли, ещё не вышли
        for _, v := range g[u] {
            if color[v] == grey {       // ребро в "серую" вершину = обратное ребро = цикл
                return true
            }
            if color[v] == white && dfs(v) {
                return true
            }
        }
        color[u] = black
        return false
    }
    for u := 0; u < V; u++ {
        if color[u] == white && dfs(u) {
            return true
        }
    }
    return false
}
// hasCycle(Graph{0: {1}, 1: {2}, 2: {0}}, 3) → true    - 0→1→2→0
// hasCycle(Graph{0: {1}, 1: {2}},          3) → false

Минимальный набор, который надо назвать

• Вставками работает за O(n²), но на почти отсортированных данных сваливается в O(n) и держит минимальную константу на коротких массивах. Поэтому живёт внутри всех промышленных гибридов.
• Слиянием даёт гарантированные O(n log n), стабильна, требует O(n) памяти. Основа внешней сортировки (когда данные не влезают в память) и легко распараллеливается.
• Быстрая: O(n log n) в среднем, O(n²) в худшем (отсортированный вход при наивном выборе опорного), in-place, лучшая константа.
• Пирамидальная гарантирует O(n log n) и O(1) памяти, нестабильна, константа хуже quicksort. Её держат как страховку от вырождения quicksort.
• Подсчётом / поразрядная обходит барьер O(n log n) за O(n + k), потому что не сравнивает элементы, а использует структуру ключа. Работает для целых в ограниченном диапазоне.

Почему O(n log n) - барьер

Любая сортировка сравнением - это дерево решений: каждое сравнение даёт один бит информации, а различить нужно n! перестановок. Высота дерева не меньше log₂(n!) ≈ n log₂ n − 1.44n. Отсюда нижняя оценка. Counting/radix её не нарушают - они просто не сравнивают.

Что внутри Go

Стабильность

Сортировка стабильна, если элементы с равными ключами сохраняют исходный относительный порядок. Практический смысл - сортировка по нескольким полям в несколько проходов: сначала по имени, затем стабильно по отделу - и внутри отдела имена останутся отсортированными. Ещё стабильность важна для воспроизводимости вывода (диффы, отчёты).

// Порядок равных элементов у нестабильной сортировки не определён:
// сегодня он один, а после смены версии Go может стать другим.
// Нужен предсказуемый - бери стабильную:
slices.SortStableFunc(rows, func(a, b Row) int { return cmp.Compare(a.Dept, b.Dept) })

// Либо один компаратор на все ключи - тогда стабильность не нужна:
slices.SortFunc(rows, func(a, b Row) int {
    if c := cmp.Compare(a.Dept, b.Dept); c != 0 {
        return c
    }
    return cmp.Compare(a.Name, b.Name)
})

// Найти индекс target или -1
func Search(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        switch {
        case a[mid] == target:
            return mid
        case a[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}

// Первая позиция, где a[i] >= target (lower bound). Универсальнее.
func LowerBound(a []int, target int) int {
    lo, hi := 0, len(a)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if a[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Первая позиция, где a[i] > target (upper bound) - тот же код со строгим сравнением
// количество вхождений target = UpperBound(a, t) - LowerBound(a, t)
// a := []int{1, 3, 3, 5, 8}
// Search(a, 5) → 3       Search(a, 4) → -1
// LowerBound(a, 3) → 1   LowerBound(a, 4) → 3   LowerBound(a, 9) → 5

Где ошибаются

1. (lo+hi)/2 вместо lo + (hi-lo)/2. На 64-битных платформах int в Go 64-битный, реально не переполнится, но это каноничная ошибка (в JDK жила девять лет), и её проверяют.
2. lo < hi при замкнутом отрезке [lo, hi] - пропускается последний кандидат, когда lo == hi.
3. lo = mid вместо lo = mid + 1 в полуинтервальной версии - при hi - lo == 1 получается mid == lo, отрезок не сокращается, бесконечный цикл.
4. Не спросили, отсортирован ли вход. Бинарный поиск требует монотонности - без неё ответ мусор.
5. Забыли про дубликаты: «найти любой» и «найти первый» - разные задачи, и именно поэтому lower bound надёжнее.

Стандартная библиотека

i := sort.SearchInts(a, x)           // lower bound; если не нашли - позиция вставки
i = sort.Search(len(a), func(i int) bool { return a[i] >= x })

idx, ok := slices.BinarySearch(a, x)                  // Go 1.21+
idx, ok = slices.BinarySearchFunc(users, u, cmpByID)  // с компаратором

sort.Search(n, f) возвращает наименьшее i из [0, n), для которого f(i) == true (или n, если такого нет), и требует, чтобы f была монотонной: false…false,true…true. Немонотонный предикат не вызовет паники - просто вернёт неверный результат.

Базовая механика

1. Считаем h = hash(key).
2. Младшие биты h дают номер бакета: bucket = h & (2^B - 1).
3. Внутри бакета ищем слот. Чтобы не сравнивать ключи целиком, сначала сверяем короткий «отпечаток» хеша (в старой мапе это tophash, старшие 8 бит; в Swiss Tables - control byte с 7 младшими битами). Полное сравнение ключей - только при совпадении отпечатка.

Коллизии: две школы

Что специфично для Go

• Рандомизация хеша. Seed свой у каждой мапы и генерируется при её создании, поэтому одна и та же последовательность ключей раскладывается по-разному на разных запусках. Это защита от HashDoS и одновременно причина, по которой порядок итерации нельзя считать стабильным (плюс рантайм ещё и стартует итерацию со случайного бакета).
• Инкрементальный рост. В старой мапе (до 1.24) при превышении load factor выделялся вдвое больший массив, но перенос делался по чуть-чуть на каждой записи и удалении (evacuate), чтобы не было длинной паузы на одной операции. В Swiss Tables мапа разбита на таблицы не больше 1024 слотов, и каждая растёт целиком за раз: пауза есть, но ограничена размером одной таблицы.
• Рост «вширь» без увеличения размера. Если элементов немного, а overflow-бакетов развелось много (последствия массовых удалений), старая мапа делала same-size grow - просто уплотнялась. В Swiss Tables overflow-бакетов нет, и такого роста тоже.
• Мапа не потокобезопасна и специально ловит конкурентную запись: fatal error: concurrent map writes - это не паника, её нельзя перехватить через recover.
• Значения мапы неадресуемы: &m[k] запрещено, а m[k].field = v для структуры не скомпилируется - потому что при росте бакеты переезжают и адрес был бы недействителен. Обходной путь - map[K]*V или «прочитал, изменил, записал обратно».