Go: Алгоритмы и структуры данных

Big O описывает верхнюю границу роста функции (время или память) от размера ввода. O(1) - константа, O(n) - линейно, O(n^2) - квадратично, O(log n) - логарифм. В Go при выборе структур и алгоритмов учитывать: поиск в map - O(1), в слайсе - O(n), бинарный поиск - O(log n); сортировка - O(n log n) для сравнений. Избегать вложенных циклов по большим данным без необходимости.

map в Go - хеш-таблица: среднее O(1) для вставки, удаления, поиска. Итерация в случайном порядке. Ключи должны быть сравниваемыми; не слайсы и не мапы. При росте мапа переаллоцируется. Проверка наличия: v, ok := m[key]. Для конкурентного доступа нужна синхронизация (mutex или sync.Map для специфичных паттернов).

m := make(map[string]int)
m["a"] = 1
if v, ok := m["b"]; ok { ... }

Связный список - узлы с указателем на следующий (и опционально на предыдущий). В Go: структура с полем next *Node. Вставка/удаление в середине O(1) при известном узле; доступ по индексу O(n). В стандартной библиотеке нет готового; container/list - двусвязный список. Применение: LRU кеш (быстрое перемещение в начало), очередь с приоритетами при частых вставках.

type Node struct { Val int; Next *Node }
func (n *Node) InsertAfter(val int) { n.Next = &Node{Val: val, Next: n.Next} }

Стек: push = append(s, x), pop = s[len(s)-1], s = s[:len(s)-1]. Очередь: на слайсе сдвиг при pop неэффективен; лучше кольцевой буфер или два стека. container/list подходит для очереди. В Go часто используют каналы как очередь горутин (блокирующая очередь). Для приоритетной очереди - heap из container/heap.

// stack
stack = append(stack, v)
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// channel as queue
ch := make(chan T, 100)
ch <- v
v := <-ch

BST: у каждого узла левое поддерево меньше, правое больше. Поиск, вставка, удаление в среднем O(log n). В Go: структура с Val, Left, Right *Node. Рекурсия или итерация с указателем на текущий узел. Балансировка (AVL, красно-черное) для гарантии O(log n). В стандартной библиотеке нет; для упорядоченного множества используют sort + бинарный поиск или сторонние деревья.

type Node struct { Key int; Left, Right *Node }
func (n *Node) Search(k int) *Node {
    if n == nil || n.Key == k { return n }
    if k < n.Key { return n.Left.Search(k) }
    return n.Right.Search(k)
}

Куча - дерево с свойством: родитель не меньше (или не больше) детей. Минимум (или максимум) за O(1), извлечение и вставка O(log n). В Go container/heap - интерфейс (Len, Less, Swap, Push, Pop); реализуют для своего типа. Используют для приоритетной очереди, сортировки heap sort, top-K элементов.

type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} { ... }
heap.Init(&h)
heap.Push(&h, 3)
min := heap.Pop(&h).(int)

BFS - очередь (слайс или канал), помечаем посещенные; обрабатываем соседей. DFS - стек (рекурсия или явный стек). В Go для графа: мапа смежности map[int][]int или структуры узлов. BFS для кратчайшего пути в невзвешенном графе. DFS для топологической сортировки, поиска циклов, компонент связности. Рекурсия с ограничением глубины или итеративный DFS для больших графов.

// BFS
queue := []int{start}
visited := map[int]bool{start: true}
for len(queue) > 0 {
    cur := queue[0]
    queue = queue[1:]
    for _, next := range graph[cur] {
        if !visited[next] { visited[next] = true; queue = append(queue, next) }
    }
}

sort.Slice, sort.SliceStable - сортировка слайса по функции Less. sort.Ints, sort.Strings - для срезов примитивов. Внутри используется introsort (O(n log n)). sort.Search - бинарный поиск в отсортированном слайсе. Кастомный тип реализует sort.Interface (Len, Less, Swap) для sort.Sort. Для больших данных с ограничением памяти - внешняя сортировка.

sort.Slice(users, func(i, j int) bool { return users[i].Age < users[j].Age })
i := sort.SearchInts(a, x)

sort.Search(n, func(i int) bool { return a[i] >= x }) возвращает минимальный индекс i, для которого условие истинно. Для поиска в отсортированном слайсе: Search возвращает позицию вставки; проверяем a[i] == x. Сложность O(log n). Условие в Search должно быть "f(i) == true => f(i+1) == true".

i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
if i < len(a) && a[i] == x { return i }
return -1

ДП - разбиение задачи на подзадачи с запоминанием результатов. Обычно таблица (слайс слайсов) или мемоизация (map). Примеры: числа Фибоначчи (F(n) = F(n-1)+F(n-2)), задача о рюкзаке, LCS, кратчайший путь. В Go: выделить слайс для состояний, заполнять в цикле или рекурсия с кешем. Порядок заполнения важен (зависимости от уже вычисленных).

dp := make([]int, n+1)
dp[0], dp[1] = 0, 1
for i := 2; i <= n; i++ { dp[i] = dp[i-1] + dp[i-2] }

LRU - вытеснение наименее недавно использованного. Структура: хеш-таблица (ключ -> узел) + двусвязный список по времени доступа. При обращении перемещать узел в голову; при переполнении удалять хвост. В Go: map + список (container/list или свой). Готовые реализации: hashicorp/golang-lru. Сложность Get/Put - O(1).

type LRU struct {
    cap  int
    m    map[string]*list.Element
    list *list.List
}
func (c *LRU) Get(key string) (interface{}, bool) {
    if e, ok := c.m[key]; ok {
        c.list.MoveToFront(e)
        return e.Value.(*item).val, true
    }
    return nil, false
}

Token bucket: буфер токенов пополняется с заданной скоростью; запрос забирает токен; при отсутствии - отказ. В Go: golang.org/x/time/rate (Limiter с Allow, Reserve). Sliding window: счетчик запросов в окне; окно двигается. Реализация: хранить метки времени запросов или приближение (счетчик + время). Fixed window проще, но возможны всплески на границах. Для распределенного лимита - Redis с INCR и EXPIRE.

limiter := rate.NewLimiter(10, 20) // 10/sec, burst 20
if !limiter.Allow() { return ErrRateLimit }