Сложность, хэш, деревья, графы — вопросы «почему так, а не иначе».
Лекции
Графы: BFS, DFS, когда что
BFS находит кратчайший путь в невзвешенном графе. DFS удобен для компонент, циклов и топологической сортировки. На бэкенде те же идеи: зависимости сервисов, DAG пайплайнов, обход оргструктур и граф вызовов.
Куча, стек, очередь, deque
Стек — LIFO, очередь — FIFO, двоичная куча отдаёт минимум или максимум за O(log n). В Go слайс закрывает стек и простую очередь, а container/heap — приоритет; куча процесса с GC к этой структуре не относится.
B-tree и почему им индексы
B-tree и B+tree держат мало уровней на диске и хорошо отвечают на равенство и диапазон. Именно поэтому обычный индекс PostgreSQL — это дерево страниц, а не бинарное дерево указателей в RAM.
Хеш-таблицы и коллизии
Хэш-таблица делит ключи по бакетам и даёт средний O(1) на поиск. Коллизии неизбежны: плохой хэш, высокий load factor и ресайз превращают константу в линейный обход и в паузы под нагрузкой.
Сложность алгоритмов и Big O
Big O описывает, как растут время и память с размером входа. На бэкенде это про индексы, N+1, аллокации и P99, а не про олимпиадную формулу с доски.