Kodlo-chan
323 lines
28 KiB
Markdown
323 lines
28 KiB
Markdown
# D1, часть 1. Сложность и хеш-таблицы (урок)
|
||
|
||
Это не проверка, а урок: сначала разбираем, потом сам решаешь. Читать сверху вниз,
|
||
код в разборах можно копировать и запускать — это образец, а не ответ на задачу.
|
||
|
||
## 1. Что такое O-нотация
|
||
|
||
O-нотация отвечает на вопрос «как растёт время работы, когда данных становится в 10 раз
|
||
больше». Константы и младшие слагаемые отбрасываются: 3n + 100 → O(n) — при n → ∞ слагаемое
|
||
100 и множитель 3 не меняют форму роста, поэтому их не пишут.
|
||
|
||
Три правила, которых хватает для 90% вопросов:
|
||
|
||
1. **Последовательные блоки складываются, остаётся старший.** O(n) + O(n²) → O(n²).
|
||
2. **Вложенные циклы перемножаются.** Цикл n по циклу n → O(n²).
|
||
3. **Деление задачи вдвое даёт log n.** Бинарный поиск в 1 000 000 элементов:
|
||
2²⁰ ≈ 1 048 576, значит 20 шагов → **O(log n), а число сравнений ≈ 20**.
|
||
|
||
Полезно помнить наизусть: `log₂(1000) ≈ 10`, `log₂(10⁶) ≈ 20`, `log₂(10⁹) ≈ 30`.
|
||
Каждое умножение данных на 1000 добавляет примерно 10 шагов — это и есть смысл log n.
|
||
|
||
**Амортизированная сложность** — средняя стоимость операции на длинной серии вызовов, а не
|
||
гарантия для каждого отдельного вызова. Механизм на примере `std::vector::push_back`:
|
||
когда выделенной памяти не хватает, вектор не увеличивает ёмкость на 1, а **удваивает** её,
|
||
выделяет новый блок и переносит туда все элементы — это разовая операция O(n). Из-за
|
||
геометрического роста ёмкости такие реаллокации случаются экспоненциально реже: после
|
||
k-й реаллокации следующая наступит примерно через 2^k новых вставок. Сумма стоимости всех
|
||
реаллокаций на n вставок — геометрическая прогрессия n/2 + n/4 + n/8 + ... ≈ n, то есть
|
||
суммарно O(n) на n операций, а не O(n²) — отсюда амортизированное **O(1)** на одну вставку.
|
||
Если бы ёмкость росла линейно (+1 каждый раз), каждая вставка копировала бы весь массив —
|
||
суммарно O(n²). Геометрический рост — не оптимизация, а необходимое условие амортизации.
|
||
Практическое следствие: реаллокация инвалидирует все указатели, ссылки и итераторы на
|
||
элементы вектора, потому что блок памяти физически переехал — источник use-after-free,
|
||
который ловит ASAN.
|
||
|
||
**Худший случай ≠ средний.** Хеш-таблица: в среднем поиск O(1), но если хеш-функция плохая
|
||
и все ключи попали в одну корзину, поиск вырождается в перебор → **O(n)**.
|
||
|
||
**Факты для карточек**
|
||
- base | Во что превращается 3n + 100 в O-нотации? — O(n)
|
||
- base | Сколько шагов у бинарного поиска в массиве из 10⁶ элементов? — 20 (log₂ 10⁶ ≈ 20)
|
||
- core | Почему push_back в среднем O(1), а не O(n)? — ёмкость растёт геометрически (удвоение), сумма реаллокаций на n вставок — геометрическая прогрессия ≈ n, а не n²
|
||
- core | Что ломает удвоение ёмкости у vector? — указатели/итераторы/ссылки на старые элементы (реаллокация переносит блок памяти)
|
||
- deep | Что будет, если ёмкость vector растить на +1 за раз вместо удвоения? — суммарная стоимость n вставок станет O(n²)
|
||
|
||
Почему дальше: если push_back амортизированно O(1) за счёт удвоения, какие структуры данных вообще гарантируют O(1) в среднем на операцию — переходим к таблице сложностей и хеш-таблицам.
|
||
|
||
## 2. Таблица сложностей, которую надо знать
|
||
|
||
| Структура | Поиск | Вставка | Удаление | Память |
|
||
|---|---|---|---|---|
|
||
| Массив (не отсортирован) | O(n) | O(1) в конец | O(n) | O(n) |
|
||
| Отсортированный массив | O(log n) | O(n) | O(n) | O(n) |
|
||
| Связный список | O(n) | O(1) по указателю | O(1) по указателю | O(n) |
|
||
| Хеш-таблица (средн.) | O(1) | O(1) | O(1) | O(n) |
|
||
| Хеш-таблица (худш.) | O(n) | O(n) | O(n) | O(n) |
|
||
| Бинарная куча | O(n) поиск | O(log n) | O(log n) удалить корень | O(n) |
|
||
| Сбалансированное BST (map) | O(log n) | O(log n) | O(log n) | O(n) |
|
||
|
||
Почему связный список даёт O(1) на вставку/удаление: если узел уже найден (есть указатель),
|
||
операция — просто перелинковка соседних указателей без сдвига остальных элементов; O(n) в
|
||
поиске появляется отдельно, потому что нет арифметики адреса — только последовательный проход.
|
||
Почему у отсортированного массива поиск O(log n), а вставка O(n): бинарный поиск делит
|
||
диапазон пополам, но вставка сдвигает все элементы после точки вставки, чтобы сохранить
|
||
непрерывность блока памяти.
|
||
|
||
Кучи отдельно: **построение из произвольного массива — O(n)** (не O(n log n) — это
|
||
частый вопрос: heapify идёт снизу вверх от середины массива к началу, и суммарная работа
|
||
по всем уровням даёт линейную оценку), вставка одного элемента — O(log n) (просеивание
|
||
вверх на высоту кучи), взятие максимума — O(1) (это корень).
|
||
|
||
Сортировки: quicksort — в среднем O(n log n), в худшем **O(n²)** (уже отсортированный
|
||
массив при плохом выборе опорного); mergesort — всегда O(n log n) и **устойчив**;
|
||
heapsort — O(n log n), неустойчив, O(1) доп. памяти. Нижняя оценка для сортировки
|
||
сравнениями — **Ω(n log n)**, быстрее сравнениями нельзя (это доказывается через дерево
|
||
решений: n! перестановок, глубина дерева бинарных сравнений — минимум log₂(n!) ≈ n log n).
|
||
|
||
Устойчивость = равные элементы сохраняют исходный порядок. Устойчивы: merge, insertion,
|
||
bubble, counting. Неустойчивы: quick, heap, selection.
|
||
|
||
**map vs unordered_map**: `map` — красно-чёрное дерево, инвариант балансировки (чередование
|
||
цветов узлов, равное число чёрных узлов на любом пути от корня до листа) держит высоту
|
||
порядка log n, отсюда O(log n) на все операции и ключи всегда в отсортированном порядке при
|
||
обходе. `unordered_map` в среднем быстрее на чистом поиске/вставке (O(1) и меньше косвенных
|
||
переходов по указателям), но не даёт упорядоченного обхода и не гарантирует порядок бакетов
|
||
между вызовами rehash.
|
||
|
||
**Факты для карточек**
|
||
- base | Сложность построения кучи (heapify) из произвольного массива? — O(n), не O(n log n)
|
||
- base | Какая сортировка всегда O(n log n) и устойчива? — mergesort
|
||
- core | Худший случай quicksort и когда он достигается? — O(n²), на уже отсортированном массиве при плохом выборе опорного
|
||
- core | Нижняя граница сортировки сравнениями? — Ω(n log n)
|
||
- core | За счёт чего map держит высоту log n? — инвариант красно-чёрного дерева: чередование цветов + равное число чёрных узлов на пути от корня до листа
|
||
- deep | Почему нельзя полагаться на порядок обхода unordered_map? — порядок бакетов не гарантирован и может меняться при rehash
|
||
|
||
Почему дальше: таблица говорит, что хеш-таблица в среднем O(1) — дальше разбираем механизм, который это обеспечивает и почему он иногда ломается до O(n).
|
||
|
||
## 3. Хеш-таблица: как устроена
|
||
|
||
Идея: по ключу считаем число (хеш) и превращаем его в индекс массива. Хотим получить
|
||
адрес за одно действие, без перебора.
|
||
|
||
Компоненты: **массив корзин**, **хеш-функция**, **правило разрешения коллизий**, **фактор
|
||
загрузки** (сколько занято от общего размера).
|
||
|
||
Коллизия — два разных ключа дали один индекс. Это норма, а не ошибка: при n ключах и m
|
||
корзинах коллизии статистически неизбежны уже при n, сравнимом с √m (парадокс дней рождения).
|
||
|
||
Два способа разрешения:
|
||
|
||
- **Цепочки (chaining):** в каждой корзине список/вектор элементов. Просто, но много
|
||
мелких аллокаций; при плохом хеше одна цепочка растёт до O(n).
|
||
- **Открытая адресация (open addressing):** все элементы лежат в самом массиве. Занято —
|
||
ищем следующую свободную ячейку по правилу: линейное зондирование `(i+1) % cap`,
|
||
квадратичное `(i + k²) % cap`, двойное хеширование `(i + k·h2) % cap`.
|
||
Быстрее по кэшу (элементы лежат подряд в памяти, меньше промахов кэша, чем при обходе
|
||
разбросанных по куче узлов списка), но есть проблема **удаления**: если просто очистить
|
||
ячейку, цепочка зондирования порвётся и поиск не найдёт элемент дальше. Решение —
|
||
**tombstone** (надгробие): помечаем ячейку «был элемент, но сейчас пусто», поиск идёт
|
||
дальше сквозь неё, а вставка может её переиспользовать. Без tombstone поиск останавливался
|
||
бы на первой пустой ячейке и не долистывал бы до элемента, который на самом деле лежит
|
||
дальше по цепочке зондирования.
|
||
|
||
**Фактор загрузки** `load = size / capacity`. При открытой адресации держат ≤ 0.7:
|
||
чем плотнее массив, тем длиннее пробеги до свободной ячейки (при load → 1 среднее число
|
||
проб на поиск растёт неограниченно). При превышении порога — **rehash**: физически
|
||
выделяется новый массив вдвое больше старого, и **каждый** элемент вставляется в него заново
|
||
по новому индексу (`hash % new_cap`), потому что индекс зависит от текущей ёмкости — старые
|
||
позиции для новой ёмкости в общем случае неверны. Это разовая операция O(n), но происходит
|
||
она редко и по той же геометрической прогрессии, что и рост `vector` (раздел 1) — отсюда
|
||
**амортизированное O(1)** на вставку, а не просто «в среднем быстро».
|
||
|
||
Почему ёмкость берут степенью двойки: тогда `idx = hash & (cap - 1)` вместо дорогого
|
||
деления по модулю — побитовое И на порядок дешевле целочисленного деления на процессоре.
|
||
Отсюда же требование: хеш-функция должна хорошо перемешивать именно младшие биты (при
|
||
делении по модулю участвуют все биты хеша, при `& (cap-1)` — только младшие log₂(cap)),
|
||
для строк — FNV-1a или `std::hash<std::string>`.
|
||
|
||
**Ловушки**
|
||
- Взять ёмкость не степенью двойки при использовании `hash & (cap-1)` → маска отрежет не те биты → часть корзин никогда не используется, видно по неравномерному распределению цепочек.
|
||
- Удалять элемент простой очисткой ячейки при открытой адресации вместо tombstone → поиск последующих элементов той же цепочки зондирования обрывается раньше времени → `get` возвращает false для существующего ключа, видно в тесте «insert A, B (коллизия с A), delete A, get B» → false.
|
||
- Не проверять load factor перед вставкой → цепочки/пробеги растут неограниченно → поиск деградирует к O(n), видно по профилировщику как рост времени `unordered_map::find` с размером таблицы.
|
||
- Пользовательский ключ с плохим/предсказуемым хешем → все элементы в одном бакете → тихая деградация до O(n) без ошибки компиляции, ловится только профилировщиком.
|
||
|
||
**Факты для карточек**
|
||
- base | Формула фактора загрузки? — load = size / capacity
|
||
- base | Порог load factor при открытой адресации, после которого делают rehash? — обычно ≤ 0.7
|
||
- core | Зачем tombstone при открытой адресации? — чтобы удаление не обрывало цепочку зондирования: поиск должен пройти сквозь помеченную ячейку до элемента, вставленного позже
|
||
- core | Почему ёмкость хеш-таблицы берут степенью двойки? — idx = hash & (cap-1) вместо деления по модулю — дешевле на процессоре
|
||
- core | Что физически происходит при rehash? — выделяется массив вдвое больше, каждый элемент переставляется по новому индексу (зависит от cap)
|
||
- deep | Почему rehash даёт амортизированное O(1), а не O(n) на вставку? — та же геометрическая прогрессия, что у vector::push_back: суммарная стоимость n вставок ≈ n, а не n²
|
||
|
||
Почему дальше: те же формулы сложности стоит применить к конкретному коду — переходим к разбору задач, где нужно на глаз определить сложность.
|
||
|
||
## 4. Разбор примера: считаем сложности
|
||
|
||
```cpp
|
||
// (а) сумма элементов
|
||
long long sum(const std::vector<int>& v) { // O(n): один проход
|
||
long long s = 0;
|
||
for (int x : v) s += x;
|
||
return s;
|
||
}
|
||
|
||
// (б) пары с суммой k
|
||
bool has_pair(const std::vector<int>& v, int k) { // O(n^2): вложенный цикл
|
||
for (size_t i = 0; i < v.size(); ++i)
|
||
for (size_t j = i + 1; j < v.size(); ++j)
|
||
if (v[i] + v[j] == k) return true;
|
||
return false;
|
||
}
|
||
|
||
// (в) то же, но через хеш-множество
|
||
bool has_pair_fast(const std::vector<int>& v, int k) { // O(n) в среднем
|
||
std::unordered_set<int> seen;
|
||
for (int x : v) {
|
||
if (seen.count(k - x)) return true; // поиск в среднем O(1)
|
||
seen.insert(x);
|
||
}
|
||
return false;
|
||
}
|
||
```
|
||
|
||
(в) — типовой ответ на собеседовании: «перебор O(n²), но с хеш-множеством получаем O(n)
|
||
за счёт O(n) дополнительной памяти». Уметь назвать и время, и память — половина ответа.
|
||
Механизм ускорения: (б) на каждой паре (i, j) делает сравнение за O(1), но пар — O(n²);
|
||
(в) вместо перебора пар один раз кладёт каждый элемент в хеш-множество (O(1) в среднем на
|
||
вставку) и один раз проверяет наличие дополнения k - x (O(1) в среднем на поиск) — итого
|
||
O(n) вставок и O(n) поисков вместо O(n²) сравнений.
|
||
|
||
**Факты для карточек**
|
||
- base | Сложность has_pair (вложенный цикл по всем парам)? — O(n²)
|
||
- core | Сложность has_pair_fast по времени и по памяти? — O(n) по времени в среднем, O(n) дополнительной памяти под хеш-множество
|
||
|
||
Почему дальше: чтобы поверить в O(1) на вставку/поиск из примера (в), нужно понять, что внутри unordered_set/unordered_map — переходим к ручной сборке хеш-таблицы.
|
||
|
||
## 5. Разбор примера: как руками собрать хеш-таблицу
|
||
|
||
Учебный минимальный вариант (это разбор, не зачётная задача — запусти и поиграйся):
|
||
|
||
```cpp
|
||
#include <cstdint>
|
||
#include <string>
|
||
#include <vector>
|
||
#include <iostream>
|
||
|
||
// 1. хеш-функция: FNV-1a, хорошо перемешивает
|
||
uint64_t fnv1a(const std::string& s) {
|
||
uint64_t h = 1469598103934665603ULL;
|
||
for (unsigned char c : s) { h ^= c; h *= 1099511628211ULL; }
|
||
return h;
|
||
}
|
||
|
||
// 2. таблица с цепочками
|
||
struct HashTable {
|
||
struct Node { std::string key; int val; Node* next; };
|
||
std::vector<Node*> buckets;
|
||
size_t sz = 0;
|
||
|
||
explicit HashTable(size_t cap = 8) : buckets(cap, nullptr) {}
|
||
|
||
size_t index(const std::string& k) const { return fnv1a(k) % buckets.size(); }
|
||
|
||
void put(const std::string& k, int v) {
|
||
Node* n = buckets[index(k)];
|
||
for (; n; n = n->next) if (n->key == k) { n->val = v; return; } // уже есть — обновляем
|
||
buckets[index(k)] = new Node{k, v, buckets[index(k)]}; // вставка в голову цепочки
|
||
++sz;
|
||
if (sz * 10 > buckets.size() * 7) rehash(); // load > 0.7
|
||
}
|
||
|
||
bool get(const std::string& k, int& out) const {
|
||
for (Node* n = buckets[index(k)]; n; n = n->next)
|
||
if (n->key == k) { out = n->val; return true; }
|
||
return false;
|
||
}
|
||
|
||
void rehash() {
|
||
std::vector<Node*> old = buckets;
|
||
buckets.assign(old.size() * 2, nullptr);
|
||
for (Node* head : old)
|
||
for (Node* n = head; n; ) {
|
||
Node* next = n->next;
|
||
size_t i = index(n->key);
|
||
n->next = buckets[i];
|
||
buckets[i] = n;
|
||
n = next;
|
||
}
|
||
}
|
||
};
|
||
```
|
||
|
||
Что здесь важно понять по шагам: `index()` — где именно ищем; `put` — сначала ищем
|
||
существующий ключ (иначе будут дубли), потом вставляем; `rehash` — заново раскладываем
|
||
**все** узлы, потому что индекс зависит от размера массива (`fnv1a(k) % buckets.size()`) —
|
||
после удвоения `buckets.size()` старый индекс для того же ключа почти всегда неверен, поэтому
|
||
пересчёт нужен для каждого узла, а не только для новых. Здесь ёмкость (8, 16, 32, ...) —
|
||
степень двойки, но индекс считается через `%`, а не `&`; замена на `hash & (cap-1)` дала бы
|
||
тот же результат быстрее, именно потому что cap — степень двойки.
|
||
|
||
Открытая адресация отличается только поиском места: вместо цепочки идём вперёд по массиву
|
||
до свободной ячейки, а при удалении ставим tombstone.
|
||
|
||
**Факты для карточек**
|
||
- base | Какие константы использует FNV-1a в этом коде (offset basis / prime)? — 1469598103934665603 / 1099511628211
|
||
- core | Почему rehash пересчитывает индекс для каждого узла, а не переносит их как есть? — индекс = hash % buckets.size(), а size() изменился (удвоился), старые индексы для нового размера в общем случае неверны
|
||
|
||
Почему дальше: разобрав таблицу вручную, полезно свести готовые формулировки ответов на типовые вопросы интервью в один блок.
|
||
|
||
## 6. Что спросят на собеседовании (готовые ответы)
|
||
|
||
- «Средняя и худшая сложность поиска в хеш-таблице?» — амортизированное O(1), худшая O(n)
|
||
при коллизиях.
|
||
- «Что такое load factor и зачем rehash?» — доля занятых ячеек; при превышении порога
|
||
(обычно 0.7–1.0) массив растёт, иначе пробеги/цепочки удлиняются.
|
||
- «Как удалять при открытой адресации?» — tombstone, иначе порвётся цепочка зондирования.
|
||
- «Почему ёмкость — степень двойки?» — `hash & (cap-1)` вместо `%`, дешевле.
|
||
- «Чем цепочки отличаются от открытой адресации?» — цепочки проще и терпят load > 1,
|
||
но аллокации; открытая адресация кэш-дружелюбнее, но требует load ≤ 0.7 и tombstone.
|
||
|
||
**Факты для карточек**
|
||
- core | Чем открытая адресация выигрывает у цепочек по производительности и почему? — она кэш-дружелюбнее: элементы лежат подряд в массиве, а не разбросаны по куче отдельными узлами
|
||
- deep | Может ли load factor у цепочек быть больше 1? — да, цепочка просто станет длиннее (в отличие от открытой адресации, где load ≤ 1 всегда)
|
||
|
||
## 7. Материалы (первопартийные)
|
||
|
||
- cppreference: `std::unordered_map`, `std::hash` — https://en.cppreference.com/w/cpp/container/unordered_map
|
||
- OSTEP, часть «Data Structures»/«Hashing» — https://pages.cs.wisc.edu/~remzi/OSTEP/
|
||
- Codeforces EDU, курс по структурам данных — https://codeforces.com/edu/courses
|
||
- Визуализация открытой адресации — https://www.cs.usfca.edu/~galles/visualization/OpenHash.html
|
||
|
||
## 8. Проверь себя (ответы внизу, не подглядывай сразу)
|
||
|
||
1. Сложность поиска в `unordered_map` в среднем и в худшем?
|
||
2. Сколько сравнений в худшем случае у бинарного поиска в массиве из 10⁶ элементов?
|
||
3. `heapify` из произвольного массива — за сколько?
|
||
4. Какая из сортировок устойчива: quick, merge, heap?
|
||
5. Зачем tombstone при открытой адресации?
|
||
6. Почему `push_back` вектора и `rehash` хеш-таблицы оба амортизированно O(1) — что у них общего в механизме?
|
||
7. Почему ёмкость хеш-таблицы удобно делать степенью двойки?
|
||
|
||
<details>
|
||
<summary>Ответы</summary>
|
||
|
||
1. Амортизированное O(1); худшая O(n) — все ключи в одной корзине.
|
||
2. 20 (`log₂ 10⁶ ≈ 20`).
|
||
3. O(n), снизу вверх от середины массива к началу.
|
||
4. merge (устойчива), quick и heap — нет.
|
||
5. Чтобы удаление не разрывало цепочку зондирования: поиск должен пройти дальше удалённой
|
||
ячейки до элемента, который был вставлен за ней.
|
||
6. Оба удваивают ёмкость при переполнении вместо роста на фиксированный шаг — редкая
|
||
операция O(n) размазывается по геометрической прогрессии вставок, суммарная стоимость
|
||
n операций ≈ n, а не n².
|
||
7. Индекс можно считать как `hash & (cap - 1)` (побитовое И) вместо деления по модулю —
|
||
дешевле для процессора.
|
||
</details>
|
||
|
||
## 9. Ссылки на задачи этого дня
|
||
|
||
- `tasks/10_hash` — своя таблица с открытой адресацией (главная задача дня, идёт ступенями).
|
||
- `tasks/01_bits` — битовые операции на C, разминка для рук.
|
||
- `tasks/03_ring` — кольцевой буфер, база для сетевого кода.
|