AlgoDS
Поиск

Ищите по-русски или по-английски.

    Меню

    Быстро вспомнить, затем вернуться к рассуждению

    Справочник

    Не набор сокращённых уроков, а навигационный слой: найдите знакомый сигнал, проверьте стоимость и границы применимости, затем откройте связанный разбор курса.

    15 тем

    Основные алгоритмы и паттерны

    Короткие ориентиры для выбора подхода: сигнал задачи, рабочая оценка и граница применимости.

    1. Разбор задачиproblem solving · brute force · переборСтроим корректный перебор, называем повторяющуюся работу и затем оптимизируем.Собственной сложности нет: сначала считают кандидатов и работу на одного кандидата, затем перемножают оценки.
    2. Линейный обходlinear scan · array traversal · линейный проходНесколько агрегатов обновляются одним чтением элемента.Один проход по n элементам: O(n) времени; дополнительная память O(1), если состояние имеет постоянный размер.
    3. Два указателяtwo pointers · два указателя · left rightПорядок позволяет безопасно убрать одну границу.Если каждый указатель движется только вперёд или внутрь диапазона, суммарное время O(n), память O(1).
    4. Скользящее окноsliding window · скользящее окно · окноПри повторе left прыгает за прошлое вхождение.При монотонных расширении и сжатии каждая граница проходит массив один раз: O(n) времени; память зависит от состояния окна.
    5. Префиксная суммаprefix sum · префиксная сумма · prefix countsСумма диапазона — разность двух префиксов.Построение O(n) времени и O(n) памяти; запрос суммы или счётчика полуинтервала после подготовки — O(1).
    6. Сортировкаsorting · sort · сортировкаСортировка превращает поиск близкой пары среди всех пар в проверку соседей.Сравнительная сортировка общего назначения обычно требует O(n log n) времени; дополнительная память зависит от алгоритма и реализации.
    7. Интервалыintervals · merge intervals · интервалыПосле сортировки по началу достаточно сравнивать новый интервал с последним уже объединённым.Сортировка n интервалов занимает O(n log n), последующий линейный проход — O(n); результат может занять O(n).
    8. Бэктрекингbacktracking · бэктрекинг · choose recurse undoПерестановка выбирает следующий неиспользованный элемент; комбинация выбирает следующий индекс только справа, а подмножество допускает include/exclude.В общем случае время экспоненциально — порядка O(b^d) для ветвления b и глубины d; стек и текущее состояние занимают O(d).
    9. Графgraph traversal · граф · dfsСписок смежности хранит только существующие рёбра и делает соседей вершины доступными за время, пропорциональное её степени.DFS и BFS по спискам смежности: O(V + E) времени и O(V) дополнительной памяти, не считая хранения графа.
    10. Топологическая сортировкаtopological sort · kahn algorithm · топологическая сортировкаАлгоритм Кана удаляет только вершины без оставшихся зависимостей; неполный результат обнаруживает цикл.Алгоритм Кана и DFS-вариант работают за O(V + E) времени и используют O(V) дополнительной памяти.
    11. Кратчайший путьshortest path · кратчайший путь · bfs distanceMulti-source BFS кладёт все источники в нулевой слой до старта и одним обходом находит расстояние до ближайшего из них.BFS для невзвешенного графа: O(V + E); Дейкстра с двоичной кучей и неотрицательными весами: O((V + E) log V).
    12. Жадный выборgreedy · жадный алгоритм · exchange argumentЖадный шаг допустим лишь тогда, когда его можно обменять на шаг из любого оптимального решения без ухудшения ответа.Цена зависит от выбора кандидата; типичная схема с предварительной сортировкой занимает O(n log n) времени.
    13. Динамическое программированиеdynamic programming · dp · динамическое программированиеМемоизация сохраняет точный ответ для каждой остаточной подзадачи и превращает повторяющееся дерево рекурсии в граф состояний.Время обычно равно числу достижимых состояний, умноженному на число переходов; память — числу хранимых состояний.
    14. Битовые операцииbit manipulation · bitmask · битовые операцииМаска с единственной единицей позволяет проверять конкретный бит, а операция x & (x - 1) удаляет младший установленный бит.Операция над машинным словом считается O(1); перебор всех масок n элементов требует O(2ⁿ), а просмотр битов каждой маски — O(n · 2ⁿ).

    10 тем

    Структуры данных

    Операционные контракты структур: что они ускоряют, сколько стоят и какой инвариант нельзя нарушить.

    1. Динамический массивdynamic array · vector · std::vectorСтоимость операции следует из внутреннего устройства контейнера: плотного массива, хеш-таблицы или очереди.Доступ по индексу O(1); добавление в конец амортизированно O(1), но отдельное расширение требует O(n); вставка и удаление внутри O(n).
    2. Хешированиеhash table · hash map · hash set`target-x` можно проверять среди уже просмотренных.Поиск, вставка и удаление ожидаемо O(1), в худшем случае O(n); память O(n).
    3. Стекstack · lifo · стекСтек хранит последнюю открытую конструкцию, которую должен закрыть следующий подходящий символ.Чтение вершины и pop с конца — O(1); push в стек поверх динамического массива амортизированно O(1), отдельное расширение — O(n); память O(n).
    4. Очередьqueue · deque · fifoДек хранит только ещё полезные элементы текущего окна и удаляет устаревшие индексы с противоположного конца.Добавление и удаление на поддерживаемых концах очереди или дека — O(1); память O(n).
    5. Монотонная структураmonotonic stack · monotonic deque · монотонный стекМонотонный стек удаляет кандидата именно тогда, когда текущий элемент впервые становится для него ответом.Каждый элемент добавляется и удаляется не более одного раза: O(n) времени и O(n) памяти в худшем случае.
    6. Связный списокlinked list · singly linked list · связный списокDummy-узел убирает особый случай первой вставки, а хвост результата всегда указывает на последний уже слитый узел.Доступ по позиции и поиск — O(n); вставка или удаление после известного узла — O(1); память O(n).
    7. Деревоtree · binary tree · деревоПоложение обработки корня относительно рекурсивных вызовов определяет preorder, inorder или postorder.Полный DFS или BFS дерева: O(n) времени; память O(h) для рекурсивного DFS и до O(w) для BFS, где h — высота, w — ширина.
    8. Кучаheap · priority queue · кучаКуча хранит частичный порядок: экстремум доступен сразу, но остальные элементы не обязаны быть полностью отсортированы.Чтение экстремума O(1), вставка и удаление экстремума O(log n), построение heapify O(n), память O(n).
    9. DSUdisjoint set union · union find · dsuDSU хранит каждую компоненту как дерево представителей и быстро поддерживает только объединения.Сжатие путей и объединение по рангу дают амортизированное O(α(n)) на find/union; память O(n).
    10. Trietrie · prefix tree · борВ trie путь от корня кодирует общий префикс, а terminal отделяет полное слово от просто существующего префикса.Вставка и поиск слова длины L занимают O(L); память пропорциональна числу созданных переходов.

    08 тем

    Продвинутые структуры и алгоритмы

    Темы после основного маршрута с явными предварительными знаниями и точными ограничениями.

    1. Классические сортировкиnon-comparison sorting · counting sort · radix sortBubble, selection, heap, counting, radix и их точные области применимости.Bubble: O(n²) в среднем и худшем случае, O(n) в лучшем с ранней остановкой; память O(1). Selection: всегда O(n²), память O(1).
    2. Fenwick и дерево отрезковrange queries · fenwick tree · segment treeИзменяемые префиксы и запросы на диапазоне.Fenwick: префиксный запрос и точечное обновление O(log n), память O(n); специальное построение возможно за O(n).
    3. LCA и сбалансированные деревьяlowest common ancestor · lca · binary liftingПредки, AVL и красно-чёрные деревья на уровне корректных инвариантов.LCA с binary lifting: подготовка O(n log n), запрос и подъём O(log n), память O(n log n).
    4. Продвинутые алгоритмы на графахadvanced graph algorithms · mst · bellman fordMST, Bellman–Ford, Floyd–Warshall, SCC, мосты и точки сочленения.Kruskal: O(m log m) времени и O(n) памяти помимо рёбер. Prim с двоичной кучей: O((n + m) log n) времени и O(n + m) памяти.
    5. Продвинутое DPadvanced dynamic programming · interval dp · bitmask dpИнтервальное, битмасочное и древесное DP.Типичное интервальное DP с перебором точки разбиения: O(n³) времени и O(n²) памяти; без перебора разбиения конкретная рекуррентность может дать O(n²).
    6. Алгоритмическая математикаalgorithmic math · gcd · modular arithmeticНОД, модульная арифметика, решето и быстрое возведение в степень.Алгоритм Евклида: O(log min(|a|, |b|)) времени и O(1) памяти в итеративной форме.
    7. Meet in the middlemeet in the middle · mitm · разделение перебора пополамРазделение экспоненциального перебора на две половины с явной оценкой памяти.Генерация состояний двух половин: O(2^(n/2)) времени и памяти с точностью до постоянного множителя.