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

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

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

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

Основы

  1. Зачем нужны структуры данных и алгоритмы — что это такое, три роли структур, обзор и базовые термины.
  2. Массивы, двоичный поиск и O-нотация — самый простой контейнер и то, как измеряют скорость: O(1), O(N), O(log N).
  3. Простая сортировка: пузырёк, выбор, вставка — три базовых алгоритма 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. Как выбрать структуру данных — сводка раздела и практическое руководство, что брать под какую задачу.

Связанное