Главная › Алгоритмы и структуры данных

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

Алгоритмы и структуры данных с нуля: массивы и сортировка, стеки, очереди, списки, рекурсия, деревья, хеш-таблицы, кучи и графы, а также приёмы решения задач — два указателя, скользящее окно, префиксные суммы, динамическое программирование.

Раздел — для тех, кто хочет разобраться в основах алгоритмов и структур данных с нуля и простыми словами. Двадцать две статьи идут от простого к сложному: сначала массивы и сортировка, потом структуры-инструменты, деревья, хеш-таблицы и, наконец, графы. У каждой структуры разбираем, что она делает быстро, что медленно и почему, — и всё это на общей мерке скорости, O-нотации. Читать удобнее по порядку, но каждая статья самодостаточна.

Основы

  1. Зачем нужны структуры данных и алгоритмы — что это такое, три роли структур, обзор и базовые термины.
  2. Математика для O-нотации: логарифмы, степени и скорость роста — школьная вспоминалка: степени, логарифмы и как из них читается O(...).
  3. Массивы, двоичный поиск и O-нотация — самый простой контейнер и то, как измеряют скорость: O(1), O(N), O(log N).
  4. Простая сортировка: пузырёк, выбор, вставка — три базовых алгоритма O(N²) и чем они отличаются.

Структуры-инструменты

  1. Стеки и очереди — LIFO и FIFO, дек и приоритетная очередь: доступ намеренно ограничен.
  2. Связанные списки — узлы и ссылки, быстрая вставка вместо быстрого доступа.
  3. Рекурсия — метод вызывает сам себя; базовое условие, стек вызовов, «разделяй и властвуй».

Быстрая сортировка

  1. Нетривиальная сортировка: Шелла, быстрая, поразрядная — как обогнать O(N²) и дойти до O(N·log N) и даже O(N).

Деревья

  1. Двоичные деревья — быстрый поиск и вставка сразу; обход, удаление, вырождение.
  2. Красно-чёрные деревья — как удержать баланс автоматически поворотами и перекраской.
  3. Деревья 2-3-4 и B-деревья — узлы с несколькими ключами; отсюда индексы баз данных.

Хеш-таблицы и кучи

  1. Хеш-таблицы — доступ по ключу за O(1); коллизии, пробирование, цепочки.
  2. Пирамиды (кучи) — мгновенный максимум, основа приоритетной очереди и heapsort.

Графы

  1. Графы — вершины и рёбра; обход в глубину и в ширину, топологическая сортировка.
  2. Взвешенные графы — минимальный остов и кратчайший путь (алгоритм Дейкстры).

Приёмы решения задач

Структуры — половина дела; вторая половина — узнавать, каким приёмом задача решается. Шесть приёмов закрывают большинство алгоритмических задач.

  1. Два указателя и скользящее окно — как заменить вложенные циклы одним проходом.
  2. Префиксные суммы — сумма любого отрезка за O(1) после одного предподсчёта.
  3. Двоичный поиск по ответу — искать не в данных, а в диапазоне ответов.
  4. Монотонный стек — вопросы «когда впервые станет больше» за один проход.
  5. Динамическое программирование — перебор, который не повторяет уже сделанную работу.
  6. Перебор с отсечением — когда нужны не число, а сами варианты.

Итог

  1. Как выбрать структуру данных — сводка раздела и практическое руководство, что брать под какую задачу.

Связанное