Углубленные алгоритмы и структуры данных: уровень MIT 6.006

Асимптотический анализ, рекуррентные соотношения и алгоритмы сортировки

Добро пожаловать в курс «Углубленные алгоритмы и структуры данных». Мы начинаем наше путешествие с фундамента, на котором строится вся современная алгоритмика: умения измерять эффективность кода и предсказывать его поведение при росте объема данных. В этой статье мы разберем асимптотический анализ, изучим классические алгоритмы сортировки и научимся решать рекуррентные соотношения.

Зачем нам нужен асимптотический анализ?

Представьте, что у вас есть два алгоритма сортировки. Один работает за 10 секунд на 1000 элементах, другой — за 20 секунд. Какой из них лучше? Ответ неочевиден, пока мы не узнаем, как меняется время работы при увеличении входных данных () до миллиона или миллиарда.

В Computer Science мы используем асимптотический анализ, чтобы описать поведение функции времени выполнения при стремлении к бесконечности. Мы абстрагируемся от конкретного «железа», языка программирования и мелких констант, сосредотачиваясь на скорости роста.

Основные асимптотические обозначения

Для формального описания сложности используются три главных символа: (О-большое), (Омега-большое) и (Тета-большое).

#### 1. -нотация (Верхняя граница)

Запись означает, что функция растет не быстрее, чем (с точностью до константы).

Формальное определение:

Где:

— время работы нашего алгоритма.

— функция сравнения (например, или ).

— положительная константа.

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

— квантор существования («существует»).

— квантор всеобщности («для всех»).

Простыми словами: это «потолок» производительности. Алгоритм не будет работать хуже этого, но может работать лучше.

#### 2. -нотация (Нижняя граница)

Запись означает, что алгоритм требует как минимум порядка операций.

Где и — константы, определяющие нижнюю границу роста функции .

#### 3. -нотация (Точная граница)

Если является одновременно и , и , то мы говорим, что . Это означает, что функции растут с одинаковой скоростью.

!Графическая иллюстрация того, как функция f(n) ограничивается сверху и снизу функцией g(n) с разными коэффициентами.

Сортировка вставками (Insertion Sort)

Рассмотрим простой алгоритм — сортировку вставками. Это то, как многие люди сортируют карты в руке: мы берем одну карту и вставляем ее в нужное место среди уже отсортированных.

Анализ сложности

В худшем случае (массив отсортирован в обратном порядке) внутренний цикл while выполняется раз для каждого шага внешнего цикла. Суммарное количество операций:

Где:

— общее время работы.

— знак суммирования.

— количество элементов в массиве.

Квадратичная сложность приемлема для малых , но катастрофична для больших данных. Если , то операций, что займет часы или дни на обычном компьютере.

Сортировка слиянием (Merge Sort) и метод «Разделяй и властвуй»

Чтобы ускорить сортировку, мы применим парадигму «Разделяй и властвуй» (Divide and Conquer). Алгоритм Merge Sort работает так:

Разделяй: Разбить массив пополам на две подзадачи.

Властвуй: Рекурсивно отсортировать две половины.

Комбинируй: Слить (Merge) два отсортированных подмассива в один.

Ключевая процедура здесь — Merge. Если у нас есть два отсортированных массива общей длиной , мы можем слить их за время , просто проходя по ним и выбирая меньший элемент.

Рекуррентное соотношение

Время работы Merge Sort описывается рекуррентной формулой:

Где:

— время сортировки массива длины .

— время на решение двух подзадач размером .

— время на слияние результатов (линейное время, где — константа).

Решение рекуррентных соотношений: Метод дерева рекурсии

Как понять, чему равно в итоге? Визуализируем это с помощью дерева рекурсии.

!Дерево рекурсии, показывающее распределение затрат на каждом уровне разбиения задачи.

Давайте посчитаем:

На уровне 0 (корень) затраты: .

На уровне 1 у нас 2 задачи по . Сумма: .

На уровне 2 у нас 4 задачи по . Сумма: .

Закономерность очевидна: на каждом уровне сумма затрат равна . Но сколько у нас уровней? Мы делим на 2, пока не дойдем до 1 (базовый случай). Количество делений — это логарифм по основанию 2.

Где — степень, в которую нужно возвести 2, чтобы получить .

Общее время работы — это (затраты на уровень) (количество уровней):

Это фундаментальный результат. Сложность значительно лучше, чем . Для , , что в 50 000 раз быстрее квадратичного алгоритма.

Заключение

Мы выяснили, что «хороший» алгоритм отличается от «плохого» не константами, а асимптотическим классом сложности. Использование рекурсии и подхода «Разделяй и властвуй» позволило нам улучшить время сортировки с квадратичного до линейно-логарифмического. В следующих статьях мы применим эти методы для анализа еще более сложных структур данных, таких как кучи (Heaps) и деревья поиска.

Хеширование, рандомизация и сбалансированные бинарные деревья поиска (AVL)

В предыдущей лекции мы разобрали алгоритмы сортировки и выяснили, что нижняя граница для сортировки сравнениями составляет . Однако часто нам не нужно сортировать все данные. Нам нужно лишь эффективно выполнять операции словаря: вставку (Insert), удаление (Delete) и поиск (Search).

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

Часть 1: Хеш-таблицы и проблема прямого доступа

Представьте, что вы хотите хранить данные о сотрудниках, используя их ID как ключ. Если ID — это числа от 0 до 99, мы можем просто создать массив A размером 100. Тогда данные сотрудника с ID 50 будут лежать в A[50]. Это называется таблицей с прямой адресацией (Direct Addressing Table). Время доступа — .

Но что, если ключи — это 64-битные целые числа? Вселенная возможных ключей имеет размер . Мы не можем выделить столько памяти. При этом реальное количество записей , которые мы хотим хранить, намного меньше .

Хеш-функции

Идея хеширования состоит в том, чтобы использовать функцию , которая отображает ключи из огромного множества в небольшое множество слотов таблицы размером .

Где:

— хеш-функция.

— вселенная всех возможных ключей.

— размер нашей хеш-таблицы (количество «корзин»).

Однако, согласно принципу Дирихле (Pigeonhole Principle), если , то неизбежно найдутся два разных ключа и , для которых . Это называется коллизией.

!Иллюстрация отображения большого пространства ключей в малую таблицу и возникновение коллизии.

Разрешение коллизий методом цепочек (Chaining)

Самый простой способ справиться с коллизиями — хранить в каждой ячейке таблицы не один элемент, а связный список (Linked List) всех элементов, хеш которых попал в эту ячейку.

Анализ сложности зависит от того, насколько хорошо хеш-функция распределяет ключи. Введем понятие коэффициента заполнения (load factor) :

Где:

(альфа) — среднее количество элементов в одной цепочке.

— общее количество хранимых элементов.

— количество слотов в таблице.

В худшем случае все ключей попадут в одну ячейку, и поиск займет . Но при простом равномерном хешировании (Simple Uniform Hashing Assumption — SUHA), где любой ключ равновероятно попадает в любую ячейку, ожидаемое время поиска составляет:

Где:

— время на вычисление хеш-функции и доступ к ячейке.

— время на просмотр списка в среднем.

Если мы выбираем пропорционально (то есть ), то , и все операции выполняются за константное время в среднем.

Часть 2: Рандомизация и Универсальное хеширование

В реальной жизни предположение о равномерности (SUHA) может не выполняться. Злоумышленник (Adversary) может узнать вашу хеш-функцию (например, ) и специально подать на вход ключи, которые дают одинаковый остаток от деления. Это превратит вашу быструю таблицу в медленный связный список, вызвав DoS-атаку (Denial of Service).

Решение — Универсальное хеширование.

Идея: не использовать одну фиксированную хеш-функцию. Вместо этого, в начале работы программы мы случайно выбираем хеш-функцию из специально спроектированного семейств функций .

Определение универсального семейства : Для любых двух различных ключей вероятность коллизии при случайном выборе не превышает :

Где:

— вероятность события.

— случайно выбранная функция.

— размер таблицы.

Это гарантирует, что никакой злоумышленник не сможет подобрать входные данные, которые ломают алгоритм, так как он не знает, какую именно функцию выберет программа при запуске.

Часть 3: Бинарные деревья поиска (BST)

Хеш-таблицы великолепны, но они не поддерживают упорядоченные операции. Вы не можете быстро найти «следующий элемент после X» или «минимальный элемент». Для этого нам нужны деревья.

Бинарное дерево поиска (Binary Search Tree, BST) — это структура, где каждый узел удовлетворяет свойству:

Все ключи в левом поддереве меньше ключа .

Все ключи в правом поддереве больше ключа .

!Пример сбалансированного бинарного дерева поиска, демонстрирующий свойство упорядоченности.

Основные операции (Search, Insert, Delete, Min, Max) выполняются за время, пропорциональное высоте дерева :

Где:

— высота дерева (длина самого длинного пути от корня до листа).

Проблема баланса

Если мы вставляем элементы в уже отсортированном порядке (1, 2, 3, 4, 5), наше дерево выродится в длинную цепочку (связный список), уходящую вправо. В этом случае , и операции замедляются до . Нам нужен механизм, который будет держать дерево невысоким, то есть сбалансированным.

Часть 4: AVL-деревья

AVL-деревья (названные в честь изобретателей Адельсона-Вельского и Ландиса) — это первые самобалансирующиеся бинарные деревья поиска. Они добавляют строгий инвариант к обычному BST.

Инвариант AVL: Для любого узла дерева высота его левого и правого поддеревьев различается не более чем на 1.

Где:

— высота левого поддерева.

— высота правого поддерева.

Почему это гарантирует логарифмическую высоту?

Пусть — минимальное количество узлов в AVL-дереве высоты . Чтобы дерево было минимально заполненным, но имело высоту , одно поддерево должно иметь высоту , а другое .

Это рекуррентное соотношение очень похоже на числа Фибоначчи. Математически доказывается, что высота AVL-дерева ограничена:

Это означает, что высота всегда остается логарифмической относительно числа узлов , гарантируя время работы для всех операций.

Балансировка через вращения (Rotations)

Когда мы вставляем или удаляем узел, инвариант AVL может нарушиться (разница высот станет равна 2). Чтобы восстановить баланс, используются вращения.

Вращение — это локальная перестройка связей в дереве, которая меняет высоты поддеревьев, но сохраняет свойство бинарного поиска (порядок элементов).

Существует два основных типа вращений:

Левое вращение (Left Rotate): Используется, когда правое поддерево слишком тяжелое.

Правое вращение (Right Rotate): Используется, когда левое поддерево слишком тяжелое.

!Визуализация правого вращения, показывающая перемещение узлов для восстановления баланса.

Все операции балансировки выполняются за константное время после вставки или удаления, так как нам нужно сделать лишь несколько вращений вверх по пути к корню.

Заключение

Мы рассмотрели два подхода к хранению данных:

Хеш-таблицы:

* Плюсы: в среднем. * Минусы: в худшем случае (без рандомизации), нет упорядоченности.

AVL-деревья:

* Плюсы: Гарантированное в худшем случае, данные упорядочены (можно искать диапазоны). * Минусы: Сложнее в реализации, больше накладных расходов на память (хранение высоты) и указатели.

Выбор между ними зависит от задачи: если нужен только быстрый поиск по точному совпадению — выбирайте хеш-таблицу. Если важен порядок данных или гарантии времени отклика — AVL-дерево будет лучшим выбором.

Графовые алгоритмы: поиск в ширину (BFS), поиск в глубину (DFS) и топологическая сортировка

В предыдущих лекциях мы изучили линейные структуры данных, хеш-таблицы и деревья. Деревья — это мощный инструмент, но они имеют строгое иерархическое ограничение: у каждого узла есть только один родитель (кроме корня), и циклы запрещены.

Однако реальный мир гораздо сложнее. Интернет, социальные сети, карты дорог, зависимости программных пакетов — все это описывается более общей структурой, называемой графом. Сегодня мы переходим к изучению фундаментальных алгоритмов обхода графов, которые станут базой для решения сложнейших задач, от навигации до искусственного интеллекта.

Что такое граф?

Формально граф определяется как пара множеств:

Где:

— граф.

— множество вершин (Vertices), или узлов.

— множество ребер (Edges), соединяющих пары вершин.

Графы бывают двух основных типов:

Ориентированные (Directed): Ребра имеют направление (стрелки). Если есть ребро , мы можем пройти от к , но не обязательно обратно.

Неориентированные (Undirected): Ребра — это двусторонние связи. Ребро означает, что можно пройти и от к , и от к .

Представление графа в памяти

Выбор структуры данных для хранения графа критически влияет на производительность алгоритмов. Существует два основных способа:

Матрица смежности (Adjacency Matrix): Двумерный массив размером , где , если есть ребро между и . Проверка наличия ребра занимает , но требует памяти.

Списки смежности (Adjacency Lists): Массив списков, где для каждой вершины хранится список всех вершин , в которые ведет ребро из . Требует памяти.

В большинстве алгоритмических задач, включая те, что мы рассмотрим сегодня, используются списки смежности, так как реальные графы часто бывают разреженными (количество ребер намного меньше ).

Поиск в ширину (Breadth-First Search, BFS)

Поиск в ширину — это алгоритм обхода, который исследует граф «слоями». Представьте, что вы бросили камень в воду: круги расходятся равномерно во все стороны. BFS работает так же: сначала посещает стартовую вершину , затем всех ее соседей (расстояние 1), затем соседей соседей (расстояние 2) и так далее.

Алгоритм BFS

Ключевая структура данных для BFS — это очередь (Queue), работающая по принципу FIFO (First In, First Out — первым вошел, первым вышел).

Поместить стартовую вершину в очередь и пометить как посещенную.

Пока очередь не пуста:

* Извлечь вершину из начала очереди. * Для каждого соседа вершины : * Если еще не посещена: * Пометить как посещенную. * Записать расстояние . * Добавить в конец очереди.

!Визуализация работы BFS: вершины исследуются слоями, удаляясь от источника.

Свойства и сложность BFS

Самое важное свойство BFS: в невзвешенном графе (где длина каждого ребра равна 1) он находит кратчайший путь от стартовой вершины до любой другой достижимой вершины.

Временная сложность:

Где:

— количество вершин (каждая вершина попадает в очередь и извлекается из нее ровно один раз).

— количество ребер (список смежности каждой вершины просматривается один раз).

Поиск в глубину (Depth-First Search, DFS)

Если BFS исследует граф осторожно, слой за слоем, то поиск в глубину (DFS) действует агрессивно. Это похоже на прохождение лабиринта по правилу «держаться правой руки»: мы идем по пути так далеко, как только можем, и возвращаемся назад (backtrack) только тогда, когда заходим в тупик.

Алгоритм DFS

DFS обычно реализуется с помощью рекурсии (используя системный стек вызовов) или явно через структуру данных стек (LIFO — Last In, First Out).

Общая схема рекурсивного DFS:

Временные метки и классификация ребер

DFS предоставляет нам мощный инструмент анализа структуры графа через временные метки:

Время входа (): момент, когда мы впервые обнаружили вершину.

Время выхода (): момент, когда мы закончили обработку всех соседей вершины и возвращаемся назад.

Эти метки позволяют классифицировать ребра: * Ребра дерева (Tree edges): ведут в новые, непосещенные вершины. * Обратные ребра (Back edges): ведут в предка в дереве обхода (указывают на наличие цикла). * Прямые ребра (Forward edges): ведут в потомка, который уже был полностью обработан. * Перекрестные ребра (Cross edges): соединяют вершины, не являющиеся предками или потомками друг друга.

!Дерево обхода DFS с классификацией ребер и временными метками.

Сложность DFS такая же, как у BFS:

Где и — количество вершин и ребер соответственно. Мы посещаем каждый узел и проходим по каждому ребру константное количество раз.

Топологическая сортировка (Topological Sort)

Представьте, что вы собираетесь одеться. Вы не можете надеть ботинки, пока не надели носки. Вы не можете надеть пиджак, пока не надели рубашку. Это пример зависимостей.

В терминах графов это задача для ориентированного ациклического графа (DAG — Directed Acyclic Graph). Если есть ребро , это значит, что задача должна быть выполнена до задачи .

Топологическая сортировка — это линейное упорядочивание всех вершин графа так, что для любого ребра вершина идет в списке раньше вершины .

Алгоритм на основе DFS

Удивительно, но топологическую сортировку можно получить, просто запустив DFS и посмотрев на время выхода .

Логика: Вершина считается «полностью обработанной» (время ), только когда все её потомки (зависимости) уже обработаны. Значит, в списке зависимостей она должна стоять раньше, чем её потомки, но алгоритм завершает её позже.

Алгоритм:

Выполнить DFS для всего графа.

Каждый раз, когда вершина получает статус FINISHED (время ), добавить её в начало связного списка.

Полученный список и есть топологическая сортировка.

Фактически, это сортировка вершин по убыванию времени выхода .

Корректность

Если граф содержит цикл, топологическая сортировка невозможна (нельзя надеть носки перед ботинками, если для носков нужны ботинки). DFS обнаружит это через наличие обратного ребра.

Сложность топологической сортировки:

Где и — элементы графа. Это линейное время, что делает алгоритм крайне эффективным для планирования задач, компиляции проектов (Makefile) и разрешения зависимостей.

Заключение

Мы разобрали два кита графовых алгоритмов: * BFS (очередь) — находит кратчайшие пути в невзвешенных графах. * DFS (рекурсия/стек) — исследует структуру графа, находит циклы и помогает упорядочивать зависимости.

Оба алгоритма работают за линейное время . Понимание этих методов необходимо для перехода к следующему уровню: поиску кратчайших путей во взвешенных графах (алгоритм Дейкстры), который мы рассмотрим в следующей статье.

Кратчайшие пути во взвешенных графах: алгоритмы Дейкстры и Беллмана-Форда

В предыдущей лекции мы исследовали графы с помощью алгоритмов поиска в ширину (BFS) и поиска в глубину (DFS). Мы выяснили, что BFS способен находить кратчайший путь в графе. Однако, у BFS есть существенное ограничение: он работает корректно только в невзвешенных графах, где каждое ребро имеет длину 1.

В реальном мире связи редко бывают равнозначными. Дорога из точки А в точку Б может занимать 5 минут, а из А в В — 50 минут. В компьютерных сетях каналы имеют разную пропускную способность и задержку. Чтобы моделировать такие системы, нам нужны взвешенные графы.

Сегодня мы разберем два классических алгоритма для поиска кратчайших путей от одной вершины (Single-Source Shortest Paths): жадный алгоритм Дейкстры и алгоритм динамического программирования Беллмана-Форда.

Формализация задачи

Пусть дан взвешенный ориентированный граф и весовая функция:

Где:

— функция веса, сопоставляющая каждому ребру вещественное число.

— множество ребер.

— множество вещественных чисел.

Вес пути определяется как сумма весов составляющих его ребер:

Где:

— суммарный вес пути.

— знак суммирования по всем ребрам пути.

— вес конкретного ребра между соседними вершинами в пути.

Наша цель — найти путь с минимальным суммарным весом от стартовой вершины до всех остальных вершин .

Ключевая концепция: Релаксация (Relaxation)

И алгоритм Дейкстры, и алгоритм Беллмана-Форда опираются на одну и ту же фундаментальную операцию, называемую релаксацией ребра.

Для каждой вершины мы будем хранить атрибут — верхнюю оценку кратчайшего пути от старта до . Изначально , а для всех остальных вершин .

Релаксация ребра проверяет, можем ли мы улучшить путь до , пройдя через . Если путь через короче текущего известного пути до , мы обновляем значение .

Формально процесс релаксации выглядит так:

Где:

— текущая оценка кратчайшего расстояния до вершины .

— текущая оценка кратчайшего расстояния до вершины .

— вес ребра, соединяющего и .

— функция выбора минимального значения.

!Визуализация того, как путь через вершину u улучшает расстояние до вершины v.

Алгоритм Дейкстры (Dijkstra's Algorithm)

Алгоритм Дейкстры — это жадный алгоритм. Он очень похож на BFS, но вместо обычной очереди FIFO использует очередь с приоритетом (Priority Queue).

Основная идея

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

Важное ограничение: Алгоритм Дейкстры работает корректно только при неотрицательных весах ребер (). Если в графе есть ребра с отрицательным весом, жадный выбор может привести к ошибке.

Псевдокод

Анализ сложности

Сложность алгоритма зависит от реализации очереди с приоритетом. В классическом варианте используется бинарная куча (Binary Heap).

Операция extract_min выполняется один раз для каждой вершины: .

Операция decrease_key (внутри релаксации) может выполняться для каждого ребра: .

Итоговая сложность:

Где:

— количество вершин.

— количество ребер.

— стоимость операций в бинарной куче.

Для плотных графов () это дает . Если использовать более сложную структуру данных — Фибоначчиеву кучу, сложность можно улучшить до , но на практике бинарная куча часто работает быстрее из-за меньших констант.

Алгоритм Беллмана-Форда (Bellman-Ford Algorithm)

Что делать, если в графе есть отрицательные веса? Например, в финансовом графе, где вершины — валюты, а ребра — обменные курсы, логарифм курса может быть отрицательным. Или в логистике, где «стоимость» может быть бонусом.

Здесь на помощь приходит алгоритм Беллмана-Форда. Он более универсален, но работает медленнее.

Основная идея

Вместо жадного выбора ближайшей вершины, Беллман-Форд просто релаксирует все ребра графа. И делает это много раз.

Сколько раз нужно релаксировать все ребра? Кратчайший путь в графе без циклов (или без отрицательных циклов) может содержать максимум ребер. Поэтому, если мы проведем релаксацию всех ребер раз, мы гарантированно распространим информацию о кратчайших путях от старта до любой вершины, даже если путь проходит через весь граф.

Псевдокод

Отрицательные циклы

Особая сила алгоритма Беллмана-Форда — способность обнаруживать отрицательные циклы. Это циклы, сумма весов в которых меньше нуля. Если такой цикл достижим из старта, то кратчайшего пути не существует, так как мы можем бесконечно крутиться по циклу, уменьшая общий вес до .

Алгоритм делает проверку после основного цикла (строки Проверка на наличие...). Если после итераций мы все еще можем успешно релаксировать какое-то ребро, значит, в графе есть отрицательный цикл.

!Иллюстрация отрицательного цикла, где каждый проход уменьшает общую стоимость пути.

Анализ сложности

Структура алгоритма проста: вложенный цикл.

Внешний цикл выполняется раз.

Внутренний цикл проходит по всем ребрам.

Итоговая сложность:

Где:

— количество вершин.

— количество ребер.

Это значительно медленнее Дейкстры ( против ), особенно для плотных графов. Однако это плата за возможность работать с отрицательными весами.

Сравнение алгоритмов

Подведем итог и сравним изученные методы поиска кратчайших путей.

| Алгоритм | Тип графа | Веса ребер | Сложность | Примечание | | :--- | :--- | :--- | :--- | :--- | | BFS | Любой | Равные (1) | | Самый быстрый для невзвешенных графов | | Дейкстра | Любой | | | Стандарт де-факто для навигации (карты) | | Беллман-Форд | Любой | Любые | | Умеет находить отрицательные циклы |

Заключение

Мы перешли от простой топологии графов к метрическим свойствам, научившись находить оптимальные маршруты с учетом стоимости перемещения.

Алгоритм Дейкстры — это пример эффективности жадного подхода, который работает благодаря отсутствию «подвохов» в виде отрицательных ребер. Алгоритм Беллмана-Форда демонстрирует мощь итеративного подхода (динамического программирования), жертвуя скоростью ради надежности и общности.

В следующей лекции мы завершим тему графов, рассмотрев задачу о минимальном остовном дереве (MST) и алгоритмы Прима и Краскала, которые позволят нам соединить все вершины графа с минимальными затратами.

Динамическое программирование: мемоизация, задачи о рюкзаке и оптимизация подструктур

Добро пожаловать обратно. В предыдущих лекциях мы прошли путь от простых сортировок до сложных графовых алгоритмов, таких как Дейкстра и Беллман-Форд. Кстати, если вы внимательно следили за алгоритмом Беллмана-Форда, вы уже видели динамическое программирование в действии, даже если мы не называли его так явно.

Сегодня мы формализуем этот метод. Динамическое программирование (DP) — это, пожалуй, самый мощный инструмент в арсенале алгоритмиста. Это метод решения сложных задач путем разбиения их на более простые подзадачи, решения каждой подзадачи всего один раз и сохранения их ответов.

Что такое динамическое программирование?

Название «динамическое программирование» было придумано Ричардом Беллманом в 1950-х годах. Слово «программирование» здесь означает не написание кода, а «планирование» (как в линейном программировании).

Чтобы задачу можно было решить методом DP, она должна обладать двумя ключевыми свойствами:

Оптимальная подструктура (Optimal Substructure): Оптимальное решение глобальной задачи можно составить из оптимальных решений её подзадач. Например, кратчайший путь из А в С через В состоит из кратчайшего пути А-В и кратчайшего пути В-С.

Перекрывающиеся подзадачи (Overlapping Subproblems): В процессе решения мы многократно обращаемся к одним и тем же подзадачам. Это отличает DP от метода «Разделяй и властвуй» (как в Merge Sort), где подзадачи обычно уникальны.

Пример 1: Числа Фибоначчи и Мемоизация

Классический пример для введения в DP — вычисление -го числа Фибоначчи. Формула известна всем:

Где:

— искомое число Фибоначчи.

— предыдущее число.

— пред-предыдущее число.

Базовые случаи: .

Наивный рекурсивный подход

Если мы запустим этот код для , дерево вызовов будет выглядеть так:

!Дерево рекурсивных вызовов, демонстрирующее многократное повторное вычисление одних и тех же значений.

Заметьте, что fib(3) вычисляется дважды, fib(2) — трижды. Сложность этого алгоритма растет экспоненциально:

Где:

— время выполнения.

— показательная функция, означающая удвоение времени работы при увеличении на 1.

Мемоизация (Top-Down DP)

Идея мемоизации проста: давайте заведем записную книжку (хеш-таблицу или массив) и будем записывать туда результаты. Перед тем как вычислять fib(k), мы проверим, нет ли уже ответа в книжке.

Теперь мы вычисляем каждое значение ровно один раз. Сложность падает с экспоненциальной до линейной:

Где — номер числа Фибоначчи.

Табуляция (Bottom-Up DP)

Вместо рекурсии мы можем заполнять таблицу от начала до конца. Это избавляет нас от накладных расходов на вызов функций (переполнение стека).

Это и есть суть динамического программирования: тщательный перебор всех состояний в правильном порядке.

Пример 2: Задача о рюкзаке (0/1 Knapsack Problem)

Перейдем к более сложной и практической задаче. Представьте, что вы вор, пробравшийся в сокровищницу. У вас есть рюкзак вместимостью килограмм. Перед вами предметов, каждый имеет вес и стоимость . Какие предметы взять, чтобы максимизировать общую стоимость, не порвав рюкзак?

Важное условие «0/1» означает, что предмет можно либо взять целиком (1), либо не брать вовсе (0). Ломать предметы нельзя.

Почему жадный алгоритм не работает?

Интуиция подсказывает: «Бери предметы с максимальной удельной стоимостью ()».

Контрпример:

Рюкзак кг.

Предмет А: вес 10, цена 60 (удельная 6).

Предмет Б: вес 20, цена 100 (удельная 5).

Предмет В: вес 30, цена 120 (удельная 4).

Жадный алгоритм возьмет А (осталось 40 кг), затем Б (осталось 20 кг). В не влезает. Итог: 160. Оптимальное решение: взять Б и В. Вес 50, цена 220.

Подход DP: Определение состояния

Чтобы решить задачу, нам нужно определить состояние. Состояние должно содержать достаточно информации, чтобы принять решение о будущем.

Пусть — это максимальная стоимость, которую можно получить, рассматривая только первые предметов и имея доступную вместимость рюкзака .

Рекуррентное соотношение

Для каждого предмета у нас есть два выбора:

Не брать предмет. Тогда максимальная стоимость равна тому, что мы могли получить, имея предметов и ту же вместимость .

Взять предмет. Мы получаем его стоимость , но вместимость рюкзака уменьшается на его вес . Этот вариант возможен только если .

Формула перехода:

Где:

— максимальная ценность для первых предметов при весе .

— ценность, если мы пропускаем -й предмет.

— оптимальная ценность для оставшегося места после взятия предмета.

— стоимость текущего -го предмета.

— вес текущего -го предмета.

— функция выбора лучшего из двух вариантов.

Визуализация таблицы

Мы строим таблицу размером .

!Схема заполнения таблицы динамического программирования, показывающая зависимость текущего состояния от предыдущих.

Анализ сложности

Мы заполняем таблицу размером . Каждая ячейка вычисляется за константное время .

Где:

— количество предметов.

— вместимость рюкзака.

Важное замечание: Это время называется псевдополиномиальным. Если очень велико (например, ), алгоритм будет работать медленно. Сложность зависит не от количества бит, необходимых для записи числа (что было бы ), а от самого значения .

Связь с графами (DAG)

Любую задачу динамического программирования можно представить как поиск пути в ориентированном ациклическом графе (DAG — Directed Acyclic Graph).

Вершины графа — это состояния (например, пары в задаче о рюкзаке).

Ребра — это переходы между состояниями (взять предмет или не взять).

Веса ребер — это стоимость или затраты перехода.

Решение задачи DP эквивалентно поиску самого длинного (или короткого) пути в этом графе. Поскольку граф ациклический, мы можем просто перебирать вершины в топологическом порядке. Именно это мы и делаем, когда пишем вложенные циклы for.

5 шагов для решения любой задачи DP

Чтобы решить задачу на собеседовании или в проекте, следуйте этому алгоритму:

Определите подзадачи. Что такое «состояние»? Сколько параметров нужно, чтобы описать ситуацию?

Угадайте (часть решения). Какой выбор мы делаем на каждом шаге? (Взять/не взять, вставить/удалить символ и т.д.)

Свяжите подзадачи. Напишите рекуррентную формулу (Recurrence relation).

Рекурсия + Мемоизация или Таблица. Выберите способ реализации.

Решите оригинальную задачу. Как ответ на подзадачу превращается в ответ на вопрос (обычно это значение в последней ячейке таблицы).

Заключение

Динамическое программирование — это не магия, а просто «умная рекурсия» или «поиск пути в DAG». Мы меняем экспоненциальный перебор на полиномиальное заполнение таблиц, жертвуя памятью ради скорости.

В следующей лекции мы рассмотрим более сложные структуры данных, такие как деревья отрезков, которые позволяют динамически обрабатывать запросы на массивах.