# конспект · шаг 1 из 1
Сводная шпаргалка: алгоритмы и структуры данных
Весь курс на одной странице: порядок работы, бюджет, структуры, алгоритмы с ценой и условием и карта «что делать, если». Это лист, который открывают через полгода вместо того, чтобы перечитывать курс. Номер в последней колонке - раздел, где тема разобрана с примером и задачей.
Модель за десять строк
просьба -> спецификация: вход, вид ответа, «лучше», края (1, 26)
-> размер и бюджет: какой класс вообще возможен (2, 26)
-> объект: перестановка, подмножество, граф, ... (26)
-> известная задача? сведение, условие метода (26)
-> структура под частые операции (4-9, 25)
-> алгоритм и его гарантия (5-23)
-> доказательство / сертификат / стресс-тест (1, 26)
-> трудно или неразрешимо? приближение / предел (21, 22)
-> замер: профиль, тест удвоения, честный повтор (25, 27)
Пять правил
- Спецификация раньше кода. Одна фраза прячет несколько задач - выбери толкование явно.
- Сначала класс, потом константа. Не проходит в тысячу раз - другой алгоритм; в разы - замер.
- Структура - по операциям и их частоте, и её гарантия держится на допущении о данных.
- Быстрое сверяют с перебором на маленьких входах и на границах кодировок.
- У каждой гарантии - способ: доказательство, сертификат, тест или предел.
Бюджет: сколько n выдержит класс
| сложность | n при 10⁷ операций (Python, секунда) |
при 10⁹ (компилируемый код) |
|---|---|---|
n |
10 000 000 | 1 000 000 000 |
n log n |
526 172 | 39 620 077 |
n² |
3162 | 31 622 |
n³ |
215 | 1000 |
2ⁿ · n |
19 | 25 |
n! |
10 | 12 |
Структуры данных
| нужно часто | структура | цена | оговорка | раздел |
|---|---|---|---|---|
| доступ по номеру, дописать в конец | динамический массив | 1, конец 1 амортизированно |
вставка в середину - n |
3, 4 |
| добавить / снять с краёв | стек, очередь, дек | 1 |
list.pop(0) в Python - n |
4 |
| есть ли ключ, значение по ключу | хеш-таблица | 1 в среднем |
худший случай n, порядка нет |
7 |
| порядок, предшественник, диапазон | сбалансированное дерево | log n |
без балансировки - n |
8 |
| много данных на диске | B-дерево | log_B n чтений |
узел = блок диска | 8 |
| минимум, вставка | двоичная куча | log n |
поиск по ключу - n |
9 |
| объединить, «в одной ли группе» | непересекающиеся множества | почти 1 амортизированно |
только объединение, без разделения | 9 |
| сумма на отрезке с изменениями | дерево Фенвика, дерево отрезков | log n |
Фенвик - по префиксам | 8 |
| ранг, «k-й», при изменениях | дерево с размерами, Фенвик по значениям | log n |
значения сжимают | 8, 27 |
| «есть ли» с ошибкой в одну сторону | фильтр Блума | k хешей |
ложные «есть» | 20 |
| сколько различных, частоты в потоке | HyperLogLog, count-min | память O(1) от потока |
ответ приближённый | 20 |
| точки рядом, поиск в области | сетка, k-d дерево, квадродерево | от плотности | скопления ломают сетку | 23 |
| старые версии без копий | персистентная структура | log n на версию |
амортизация под откатом ломается | 25 |
Алгоритмы: цена и условие
| задача | алгоритм | время | условие или граница | раздел |
|---|---|---|---|---|
| сортировка, нужна устойчивость | слияние, Timsort | n log n |
память n |
5, 25 |
| сортировка на месте | быстрая (случайный опорный) | n log n в среднем |
худший n², неустойчива |
5 |
| сортировка сравнениями вообще | - | не меньше log₂ n! |
нижняя граница | 5 |
| целые из малого диапазона | подсчётом / поразрядная | n + k / d(n + k) |
не сравнения | 5 |
| поиск в отсортированном | двоичный | log n |
монотонный признак | 6 |
| k-й по величине | быстрый выбор / медиана медиан | n в среднем / всегда |
- | 6 |
| минимизировать наибольшее | двоичный поиск по ответу | log(диапазон) · проверка |
проверка монотонна | 6, 26 |
| обход, слои, компоненты | BFS, DFS | V + E |
BFS - кратчайший при равных рёбрах | 10 |
| порядок с зависимостями | топологическая сортировка | V + E |
граф без циклов | 10 |
| мосты, точки сочленения | DFS с low |
V + E |
пропускать ребро, а не вершину | 10, 27 |
| кратчайший путь, веса ≥ 0 | Дейкстра с кучей | (V + E) log V |
отрицательные рёбра ломают | 11 |
| кратчайший к известной цели | A* | обычно раскрывает меньше Дейкстры | эвристика честная и согласованная | 11, 27 |
| отрицательные веса, циклы | Беллман-Форд | V · E |
находит отрицательный цикл | 11 |
| все пары | Флойд-Уоршелл | V³ |
- | 11 |
| минимальный остов | Крускал, Прим | E log E |
веса рёбер, граф неориентирован | 11 |
| максимальный поток | Эдмондс-Карп | V · E² |
поток = минимальный разрез | 12 |
| паросочетание в двудольном | Кун | V · E |
увеличивающие пути | 12 |
| назначение наименьшей стоимости | венгерский, поток мин. стоимости | n³ |
- | 12 |
| умножение длинных | Карацуба / БПФ | n^1,585 / n log n |
- | 13, 18 |
| ближайшая пара точек | разделяй и властвуй | n log n |
- | 13 |
| выбор, расписание, коды | жадность | обычно n log n |
нужно доказательство обменом | 14 |
| подзадачи повторяются | динамика | число подзадач × переход | рюкзак n · W - псевдополином |
15 |
комбинаторный выбор, n ≤ 20 |
перебор, ветви и границы | 2ⁿ, n! |
отсечения не меняют класс | 16 |
| ход в игре | минимакс, альфа-бета | дерево игры | порядок ходов, таблица позиций | 16, 27 |
| подстрока | КМП, Z-функция | n + m |
- | 17 |
| много образцов | Ахо-Корасик | n + m + вхождения |
считать по цепочке ссылок | 17, 27 |
| много запросов к одному тексту | суффиксный массив | n log n построение |
- | 17 |
| степень, обратный по модулю | быстрое возведение, Евклид | log |
- | 18 |
| простота большого числа | Миллер-Рабин | k · log³ |
ошибка с малой вероятностью | 18, 20 |
| выпуклая оболочка | Эндрю, Грэхем | n log n |
поворот - знак векторного произведения | 23 |
| пересечения отрезков | заметание | (n + k) log n |
точность на границах | 23 |
| данные не в память | внешняя сортировка | (N/B) · log_(M/B)(N/B) передач блоков |
обычно один-два прохода слияния | 24 |
Что делать, если
задача NP-трудна (раздел 21)
├── n мало -> точный перебор, динамика по маскам
├── нужна гарантия -> приближение (вершинное покрытие ×2)
├── гарантии нет, нужно хорошо -> локальный поиск, отжиг
└── особый класс входов -> параметр, древесная ширина
задача неразрешима -> предел снаружи (шаги, время)
ответ слишком большой -> «сколько» вместо «все»
быстрое расходится с перебором -> уменьшить контрпример
эталона нет -> сертификат, инвариант, метаморфные
не укладывается в бюджет -> профиль, затем тест удвоения
сравнение дробных у нуля -> допуск между ошибкой и сигналом
случайность нужна честная -> выборка с отказом, закреплённое семя
Ловушки джокера
Хеш-таблица «всегда за единицу». В среднем - да; на подобранных ключах - линия.
Дейкстра с отрицательным ребром. Ответ правдоподобный и неверный, без единой ошибки.
Жадность без обмена. Красиво, быстро и неверно на контрпримере из трёх элементов.
Рюкзак «полиномиален». Таблица растёт с величиной вместимости, а не с длиной её записи.
list.pop(0) в цикле. Очередь на списке Python - квадрат.
Тест на маленьких числах как гарантия. Ошибки упаковки живут на границах.
% m на равномерных байтах. Смещение, если размер области не делится на m.
Где всё это встретилось вместе
Финальный проект «Архипелаг» (раздел 27) - карта применения: пещеры - случайный остов на
непересекающихся множествах, мосты - DFS с low, путь - A* и поле расстояний, туман - прямая
Брезенхема, рецепты - динамика по графу без циклов, трюм - рюкзак, рынок - отрицательный цикл, рейтинг -
Фенвик, соперники - сортировка и паросочетание, чат - Ахо-Корасик, сохранения - хеш Зобриста, ИИ -
альфа-бета, моды - предел шагов, сервер - инварианты и профиль. Если тема из таблицы забылась, проще всего
вспомнить её по механике игры.
Развилки по модели задачи
| Ситуация | Что проверить |
|---|---|
| Неравные рекуррентности | Акра-Бацци; точный показатель внутри Θ |
| Линейный переход | Степень матрицы; размер состояния и модуль вычислений |
| Малое решение | Сжатие FVS, ядра, динамика по ширине |
| Случайные данные | Отделяй распределение, независимость и смысл вероятностной гарантии |
| Схемы, память, диалог | Неравномерность, чередование и интерактивность меняют класс модели |
| Геометрический запрос | Ориентация, вырожденность и форма диапазона меняют гарантию |
| Параллельность | Считай работу, глубину, согласованность и цену обмена отдельно |
| Сохранение версии | Мемоизация, расписание и валидация зависимостей решают разные задачи |
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий