Здравствуйте, друзья! В сегодняшней статье мы поговорим про алгоритмы и структуры данных – ключевые фундаментальные знания для любого программиста. Мы подготовили большой FAQ, где простыми словами отвечаем на частые вопросы начинающих. Вы узнаете, что такое алгоритмы и структуры данных, почему они так важны, рассмотрим основные виды алгоритмов (сортировка, поиск, графы, динамическое программирование и др.), разберём популярные структуры данных (массивы, списки, стек, очередь, деревья, хеш-таблицы) и приведём несколько примеров реализации.

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

Итак, приступим!

Часто задаваемые вопросы по алгоритмам и структурам данных для начинающих

1. Что такое алгоритм?

Алгоритм – это точная последовательность действий или инструкций, предназначенная для выполнения определённой задачи. Проще говоря, алгоритм описывает как шаг за шагом решить ту или иную проблему. В жизни примеры алгоритмов встречаются повсюду. Например, рецепт приготовления блюда – это алгоритм (набор шагов) для получения готового блюда, а маршрут из дома до работы – тоже алгоритм, указывающий последовательность действий (повернуть направо, пройти 100 метров и т.д.). В контексте программирования алгоритм – это набор команд, который программист задаёт компьютеру для достижения результата.

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

2. Что такое структура данных?

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

Каждая структура данных предназначена для своих задач. Правильный выбор структуры позволяет экономно расходовать память и быстрее выполнять операции над данными. Современные языки программирования уже имеют реализацию многих структур данных «из коробки», и разработчику важно понимать, какую структуру когда использовать. Без структур данных сложно представить работу с большими объемами информации – они упорядочивают данные и облегчают разработку сложных программ. Говорят, что алгоритмы и структуры данных являются одной из главных составляющих в изучении программирования¹ – знание структур данных необходимо каждому разработчику.

3. Зачем нужны алгоритмы и структуры данных?

Алгоритмы и структуры данных лежат в основе эффективного программирования. Почему их важно изучать? Во-первых, они позволяют решать задачи быстрее и оптимальнее. Многую проблему можно решить «в лоб» простым перебором, но это часто долго и неэффективно. Гораздо лучше подобрать или придумать алгоритм, который уменьшит количество действий. Например, сортировку из 1000 элементов можно сделать простым переставлением элементов (что займёт десятки тысяч операций), а можно использовать более умный алгоритм, который сделает за меньшее число шагов – результат тот же, но временные затраты существенно меньше. Хороший алгоритм экономит время выполнения программы, а правильная структура данных экономит память и упрощает код.

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

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

4. Что такое сложность алгоритма?

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

Чаще всего используют нотацию O-большое (Big-O notation) для оценки сложности. Например:

• O(1) – постоянная сложность: время работы не зависит от размера данных. Пример: получение элемента массива по индексу – всегда один шаг.

• O(n) – линейная сложность: время растёт пропорционально количеству элементов n. Пример: простой проход по массиву из n элементов.

• O(n²) – квадратичная: время растёт как квадрат размера данных. Например, наивная реализация сортировки перестановками может потребовать порядка n² сравнений.

• O(log n) – логарифмическая: время растёт логарифмически. Например, бинарный поиск по отсортированному массиву за счёт деления диапазона пополам имеет сложность порядка log₂(n).

• O(n log n) – линейно-логарифмическая: распространённая сложность эффективных алгоритмов сортировки (быстрая сортировка, сортировка слиянием).

• O(2^n) или O(n!) – экспоненциальная и факториальная: очень быстро растущие времена работы, практические алгоритмы с такой сложностью способны обработать лишь небольшие n.

Временная сложность показывает, как изменится время работы алгоритма при увеличении входных данных. Например, алгоритм с O(n) при удвоении размера входа примерно удвоит время выполнения, а алгоритм с O(n²) – увеличит время в ~4 раза. Пространственная сложность аналогично оценивает, сколько памяти потребуется.

Почему важно понимать сложность: это помогает выбирать наиболее эффективные алгоритмы. В реальных задачах разница между алгоритмом O(n) и O(n²) при больших n колоссальна. Знание сложности убережёт от неэффективных решений и позволит писать код, который работает быстрее и потребляет меньше ресурсов.

5. Какие бывают виды алгоритмов?

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

• Алгоритмы сортировки – предназначены для упорядочивания данных. Примеры: пузырьковая сортировка, быстрая сортировка, сортировка слиянием.

• Алгоритмы поиска – позволяют находить нужный элемент среди данных. Например, линейный поиск (перебор всех элементов) и более эффективный двоичный поиск.

• Алгоритмы на структурах данных – специальные методы обхода и обработки структур. Например, алгоритмы обхода деревьев (префиксный, постфиксный обход) или графов (алгоритмы поиска в глубину и ширину).

• Алгоритмы на графах – выделим отдельно, это алгоритмы для задач на графах: поиск путей (алгоритм Дейкстры для кратчайшего пути), обходы графа (BFS, DFS), поиск остовного дерева и др.

• Алгоритмы оптимизации и динамического программирования – методы решения задач путем оптимального выбора (жадные алгоритмы) или разбиения задачи на подзадачи с сохранением решений (динамическое программирование).

• Алгоритмы шифрования и хеширования – для защиты данных и быстрого сравнения (например, алгоритмы шифрования AES, алгоритмы хеширования SHA).

• Алгоритмы работы с строками – поиск подстроки (алгоритм Кнута–Морриса–Пратта, Бойера–Мура), обработка текста и т.п.

• Численные алгоритмы – для математических вычислений (решение уравнений, вычисление интегралов и т.д.).

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

6. Что такое рекурсия и как она используется в алгоритмах?

Рекурсия – это способ организации алгоритма, при котором функция вызывает сама себя. Алгоритм, использующий рекурсию, решает задачу путем разбиения её на более простую подзадачу того же типа. Рекурсивная функция имеет условие выхода (базовый случай), при котором она перестаёт вызывать себя и возвращает результат напрямую, и рекурсивный случай, где функция решает часть задачи и вызывает саму себя для решения оставшейся части.

Простой пример рекурсии – вычисление факториала числа n!:

• Базовый случай: 0! = 1 (по определению).

• Рекурсивный случай: n! = n * (n-1)! при n > 0.

Реализация этого алгоритма на Python с использованием рекурсии:

В этом примере функция factorial вызывает сама себя, каждый раз уменьшая n, пока не достигнет базового случая. Рекурсия удобна для тех задач, которые естественно разделяются на аналогичные подзадачи. Кроме математических примеров (факториал, числа Фибоначчи), рекурсию часто используют для обхода деревьев и графов, обхода файловой системы, разбору вложенных структур и т.д. Например, алгоритм быстрой сортировки (QuickSort) реализован рекурсивно: массив разбивается на две части (элементы меньше опорного и больше опорного), затем каждая часть рекурсивно сортируется алгоритмом QuickSort.

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

7. Что такое сортировка и зачем сортировать данные?

Сортировка – это процесс упорядочивания элементов в коллекции (массиве, списке) по определённому критерию (например, по возрастанию чисел, в лексикографическом порядке строк и т.д.). Задача сортировки – одна из самых распространённых в программировании. Отсортированные данные легче и быстрее обрабатывать: в них проще искать элементы (в отсортированном списке можно применять быстрый двоичный поиск), их удобнее выводить пользователю в читаемом виде, можно эффективно находить дубликаты или выполнять другие операции.

Примеры, зачем нужна сортировка:

• Поиск: прежде чем искать элемент, часто данные сортируют, чтобы применить более быстрые алгоритмы поиска.

• Приведение к порядку: чтобы вывести список имен в алфавитном порядке или отсортировать товары по цене.

• Алгоритмы и структуры: некоторые алгоритмы требуют отсортированных данных (например, для эффективного слияния списков или алгоритмы на графах могут сначала сортировать рёбра по весу).

Существует множество алгоритмов сортировки. Простейшие из них, вроде пузырьковой сортировки, обучают понимать сам принцип перестановки элементов. Более сложные (QuickSort, MergeSort, HeapSort) используются на практике благодаря высокой скорости работы. Знание различных сортировок помогает понять принципы оптимизации алгоритмов в целом.

8. Как работает алгоритм пузырьковой сортировки?

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

Алгоритм пузырьковой сортировки для массива из n элементов можно описать так:

1. Повторять n-1 раз:

2. Проходить по массиву от начала до предпоследнего элемента:

3. Если текущий элемент больше следующего, поменять их местами.

4. Если за полный проход не произошло ни одной смены мест – массив уже отсортирован, можно завершать раньше.

После первого полного прохода самый большой элемент «утонет» в конец массива (окажется на своей позиції). После второго прохода второй по величине будет на предпоследней позиции и т.д. Таким образом, за i-проходов последние i элементов уже будут стоять отсортированно.

Пример реализации пузырьковой сортировки на Python для списка чисел:

Здесь внешний цикл делает несколько проходов, а внутренний цикл обменивает «неправильно» стоящие соседние элементы. Флаг swapped отслеживает, был ли хоть один обмен за проход – если нет, значит массив уже упорядочен и можно завершить работу раньше (это небольшая оптимизация алгоритма). В худшем случае пузырьковая сортировка делает порядка n² сравнений/перестановок, что при большом n неэффективно. Тем не менее, этот алгоритм важен для понимания принципов сортировки и часто используется для обучающих целей.

9. Что такое сортировка выбором (Selection Sort)?

Сортировка выбором – ещё один простой алгоритм сортировки. Его идея: на каждом шаге находить минимальный (или максимальный) элемент из неотсортированной части массива и ставить его в начало этой части. Процесс продолжается, пока не будут перебраны все элементы.

Описание алгоритма Selection Sort для сортировки по возрастанию:

1. Найти индекс минимального элемента в массиве и обменять этот элемент с первым элементом.

2. Теперь считать, что первый элемент уже отсортирован. Затем найти минимальный элемент среди оставшихся неотсортированных (со второго до конца) и обменять его со вторым элементом.

3. Повторять этот процесс: на i-й итерации находить минимальный элемент с позиции i до конца и ставить его на позицию i.

4. Когда дойдём до последнего элемента, массив будет отсортирован.

Таким образом, на первой итерации самый маленький элемент помещается на позицию 0, на второй итерации – второй по величине помещается на позицию 1 и так далее.

Пример: предположим, есть массив . Сортировка выбором сначала найдёт минимальное значение (1) и поменяет его с первым элементом. Массив станет . Затем алгоритм найдёт минимальный среди оставшихся – это 2, он уже на нужном месте (в позиции 1). Далее среди минимальный 4 – поменяем с элементом на позиции 2: массив станет . Затем среди минимальный 5 – поменяем с элементом на позиции 3: . Последний элемент 8 остаётся на месте. Массив отсортирован.

Сортировка выбором также выполняет порядка n² операций в худшем случае (т.к. на каждую позицию ищется минимум в оставшейся части). Её преимущество в том, что количество обменов элементов минимально – максимум n обменов (в каждом проходе один обмен). Однако по числу сравнений она не выигрывает у пузырьковой: оба алгоритма квадратичны. На практике Selection Sort редко используют из-за невысокой эффективности, но он помогает понять подход «выбора» минимального элемента и обмена.

10. Что такое быстрая сортировка (QuickSort) и почему она быстрая?

Быстрая сортировка (QuickSort) – один из самых эффективных и широко применяемых алгоритмов сортировки общего назначения. QuickSort работает по принципу «разделяй и властвуй» (divide and conquer). Алгоритм рекурсивно делит массив на части относительно опорного элемента (pivot) и затем сортирует каждую часть.

Как работает QuickSort (упрощённо):

1. Выбирается опорный элемент (обычно первый, последний или средний элемент массива, либо вычисленный как медиана).

2. Элементы массива перераспределяются: все, что меньше опорного, перемещаются влево от него, а все, что больше – вправо (это стадия partition, разбиение).

3. Опорный элемент оказывается на своём правильном месте в отсортированном массиве (в позиции, где слева все меньше, а справа все больше).

4. Далее алгоритм рекурсивно применяет сортировку к подмассиву слева от опорного и к подмассиву справа от опорного.

Пример: сортировка массива методом QuickSort. Пусть опорный элемент – последний (2). Разбиение: переместим все элементы меньше 2 влево, а больше – вправо. В результате массив может преобразоваться (после перестановок) в , где 2 – опорный – оказался на позиции index=1. Теперь QuickSort рекурсивно отсортирует левую часть (одноэлементный массив уже отсортирован) и правую часть . Для правой части выберется новый pivot, массив разобьётся на две части и т.д., пока все части не будут отсортированы.

Почему QuickSort быстрый? В среднем случае его сложность составляет O(n log n), что значительно лучше квадратичной O(n²) у простых алгоритмов. Разделение массива примерно пополам на каждом шаге обеспечивает логарифмическое число уровней рекурсии, а на каждом уровне происходит линейное число операций сравнения/перестановок – перемножая получаем O(n log n). Конечно, бывает и худший случай (например, если опорный элемент каждый раз выбирается самым большим или самым маленьким, QuickSort вырождается в квадратичную сортировку). Но на практике этого стараются избегать выбором хорошего опорного (например, медианы трёх элементов) и случайностью.

На практике QuickSort – один из наиболее производительных алгоритмов сортировки для больших объемов данных. В стандартных библиотеках многих языков реализованы разновидности QuickSort (правда, часто используют его модификации, устойчивые к худшим случаям). К достоинствам QuickSort относится и то, что он сортирует на месте (in-place, не требуя дополнительной памяти, кроме стека рекурсии), в отличие, например, от сортировки слиянием.

11. Что такое сортировка слиянием (Merge Sort)?

Сортировка слиянием (Merge Sort) – ещё один классический алгоритм сортировки, использующий подход «разделяй и властвуй». В отличие от QuickSort, сортировка слиянием использует другую стратегию: она рекурсивно делит массив на две половины, сортирует каждую половину, а затем сливает две отсортированные половинки в один отсортированный массив.

Как работает Merge Sort:

1. Если массив из 0 или 1 элемента – он уже отсортирован (базовый случай рекурсии).

2. Иначе рекурсивно разделяем массив на две примерно равные части.

3. Применяем Merge Sort к каждой из частей, получая два отсортированных подмассива.

4. Затем выполняется процедура слияния: берем два отсортированных списка и объединяем их в один сортированный. Для этого выделяется дополнительный временный массив, в который последовательно выбираются наименьшие текущие элементы из двух списков.

Например, массив сортируется слиянием так:

• Делим пополам -> и .

• Сортируем рекурсивно первую половину -> получим .

• Сортируем вторую половину -> получим .

• Сливаем два отсортированных списка: на выходе получаем полностью отсортированный .

Слияние двух списков происходит за время O(n) (где n – суммарный размер двух списков), т.к. мы линейно проходимся по обоим и собираем результат. Глубина рекурсии ~log₂(n) (пока делим пополам), на каждом уровне суммарно обрабатывается n элементов при слиянии, итого общая сложность Merge Sort – O(n log n) в худшем, среднем и лучшем случаях. Это отличный показатель эффективности.

Недостаток сортировки слиянием – для слияния требуется дополнительная память, пропорциональная размеру массива. Алгоритм не работает на месте, он создаёт вспомогательные списки на каждом этапе. Для больших объемов данных это может быть ощутимым минусом. Тем не менее, стабильность (не меняет относительный порядок равных элементов) и гарантированная сложность O(n log n) делают Merge Sort популярным. Он часто используется для сортировки связных списков (где QuickSort не так удобен) или в ситуациях, когда важна стабильность сортировки.

12. Какой алгоритм сортировки самый эффективный?

Не существует одного универсально «лучшего» алгоритма сортировки – все зависит от контекста. Однако можно выделить несколько аспектов при сравнении эффективности сортировок:

• Время выполнения (сложность): По этому критерию у крупных входных данных выигрывают алгоритмы с O(n log n). К ним относятся QuickSort, Merge Sort, Heap Sort. Простые алгоритмы (пузырьковый, выбором, вставками) имеют O(n²) и значительно медленнее на больших массивах.

• Память: Некоторые алгоритмы требуют дополнительную память. QuickSort и HeapSort работают на месте (не требуют значительного доп места), а Merge Sort требует O(n) дополнительной памяти для слияния. Если память ограничена, лучше использовать in-place алгоритмы.

• Стабильность: Стабильный алгоритм не изменяет порядок равных элементов. Это важно, например, при сортировке объектов по одному ключу, сохраняя порядок по другому. Merge Sort по умолчанию стабильный, QuickSort – нет (хотя есть стабильные реализации).

• Простота реализации и поддержки: Пузырьковая и сортировка вставками простейшие, QuickSort и MergeSort сложнее реализовать, но все же достаточно стандартны.

• Размер данных: Для очень небольших массивов (n десятки) разница между алгоритмами незначительна – иногда простая сортировка вставками может быть даже быстрее из-за малого константного overhead. Для огромных данных выбор алгоритма критичен.

На практике, как правило, используют встроенные функции сортировки языков, которые написаны весьма оптимально. Например, в Python стандартная сортировка (list.sort()) основана на алгоритме Timsort – это гибридный алгоритм, сочетающий идеи Merge Sort и Insertion Sort, оптимизированный под реальные данные. Он имеет сложность O(n log n) в худшем случае и работает очень эффективно на частично отсортированных данных.

Если же говорить об учебных алгоритмах: QuickSort часто оказывается самым быстрым в среднем на разнообразных данных. Однако важно помнить, что QuickSort имеет худший случай O(n²), поэтому для критичных приложений иногда предпочитают HeapSort (тяжее в реализации, но гарантированно O(n log n)). Merge Sort удобен, когда нужна стабильность или когда легко выделить доп. память. В реальных системах иногда комбинируют подходы: например, делают QuickSort, а для мелких подзадач внутри него переключаются на простую сортировку вставками.

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

13. Что такое двоичный поиск и чем он отличается от простого перебора?

Двоичный поиск (binary search) – это алгоритм поиска элемента в отсортированном массиве, который существенно быстрее перебора. При линейном (простом) переборе мы проверяем каждый элемент последовательно, пока не найдём искомый. В худшем случае придётся пройти весь список из n элементов – сложность O(n). Двоичный поиск же работает за O(log n) шагов, но требует, чтобы массив был уже отсортирован.

Идея двоичного поиска:

1. В отсортированном массиве берётся средний элемент.

2. Если средний элемент совпал с искомым – успех, элемент найден.

3. Если искомое значение меньше среднего – продолжим поиск в левой половине массива (поскольку в отсортированном списке все более крупные элементы находятся справа, и искомого среди них точно не будет).

4. Если искомое значение больше среднего – ищем в правой половине массива.

5. Повторяем процесс для соответствующей половины: каждый раз делим рассматриваемый диапазон пополам и сравниваем со средним в нём.

6. Продолжаем, пока элемент не найден, либо пока диапазон поиска не сократится до пустого (значит, элемента нет).

Пример: дан отсортированный массив , ищем число 10. Двоичный поиск сперва посмотрит на средний элемент – здесь это 7 (индекс 2). 7 меньше 10, значит искомое может быть только в правой половине (). Берём средний из этой половины – это 14. 14 больше 10, значит нужный элемент в левой части этой половины (). Там сразу находим 10. Потребовалось 3 сравнения вместо 6 при полном переборе.

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

В коде двоичный поиск можно реализовать рекурсивно или итеративно. Итеративный вариант на Python:

Здесь low и high ограничивают текущий диапазон поиска, а mid каждый раз выбирается как середина. Диапазон сужается вдвое на каждой итерации. Если элемент найден, возвращаем его индекс, иначе по выходу из цикла можно вернуть, например, -1 (как признак отсутствия). Двоичный поиск очень эффективен: даже для миллиона элементов потребуется около log2(1,000,000) ≈ 20 сравнений, тогда как линейному поиску в худшем случае пришлось бы 1,000,000 сравнений.

14. Что такое массив?

Массив – это простейшая и одна из наиболее используемых структур данных. Массив представляет собой набор элементов, расположенных подряд в памяти, где каждому элементу соответствует индекс (номер позиции). Благодаря этому индексированному доступу к любому элементу массива можно обратиться напрямую за постоянное время O(1) – достаточно знать его индекс.

Ключевые свойства массива:

• Элементы хранятся последовательно друг за другом.

• Индексы обычно начинаются с 0 (в большинстве языков программирования) и идут подряд 0, 1, 2, ... до размера массива минус 1.

• Все элементы массива, как правило, одного типа (например, массив целых чисел или массив строк).

Пример: массив целых чисел из 5 элементов может выглядеть так:
Индексы: 0 1 2 3 4
Значения:
Здесь arr = 10, arr = 5 и т.д.

Плюсы массива:

• Быстрый доступ по индексу: как уже упомянуто, прочитать или изменить значение по известному индексу можно мгновенно.

• Простота: массивы напрямую поддерживаются многими языками, с ними легко работать.

Минусы:

• Фиксированный размер (в классическом понимании массива): при создании массива нужно знать или выделить определённый размер. Если массив заполнен, добавить новый элемент непросто – нужно создавать новый, больший массив и копировать данные. (В высокоуровневых языках есть динамические массивы/списки, которые автоматически расширяются, но внутри они реализованы через переразмещение и копирование).

• Дорогие вставки/удаления в середине: если нужно вставить элемент в середину массива, придётся сдвигать все последующие элементы вправо, что занимает O(n) времени. Удаление аналогично – сдвигает элементы влево.

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

Массивы подходят, когда вы знаете нужный размер или можете заранее зарезервировать с запасом, и когда требуются быстрые чтение/запись по индексам. Почти во всех языках программирования массивы поддерживаются «из коробки». Динамические структуры вроде списков Python или ArrayList в Java строятся на базе массивов, автоматически управляя их расширением.

15. Что такое связный список?

Связный список – это динамическая структура данных, состоящая из узлов (элементов), каждый из которых хранит значение и ссылку (указатель) на следующий узел списка. Благодаря этому элементы списка могут располагаться в памяти не последовательно, а где угодно – их порядок задаётся связями (ссылками) между элементами.

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

Пример связного списка (односвязного) со значениями: 5 -> 8 -> 12 -> 3 -> NULL. Здесь 5 – первый элемент (голова списка). Он содержит значение 5 и ссылку на узел со значением 8. Узел 8 ссылается на 12, 12 – на 3, а 3 уже ссылается на NULL (конец списка).

Плюсы связных списков:

• Гибкость размера: список может легко расти или уменьшаться. Чтобы добавить элемент в начало, достаточно завести новый узел и ссылаться им на старую голову. Чтобы удалить из начала – достаточно изменить голову на следующий элемент.

• Вставка/удаление в произвольном месте: если у нас уже есть ссылка на место вставки, операция выполняется быстро (меняем несколько ссылок). Нет необходимости сдвигать все последующие элементы, как в массиве.

• Элементы могут находиться где угодно в памяти, не нужно непрерывного блока памяти.

Минусы:

• Медленный доступ по индексу: чтобы прочитать значение k-го элемента, надо начать с начала списка и пройти k шагов по ссылкам. Случайный доступ занимает O(n) в среднем, что намного медленнее, чем O(1) у массива.

• Дополнительная память на ссылки: каждый элемент хранит ещё указатель (или два в двусвязном), что увеличивает потребление памяти.

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

Связные списки используются там, где нужны часто вставки/удаления, особенно в начало структуры (например, реализация очередей, стеков, отслеживание истории переходов и т.п.), а случайный доступ не столь важен. Также на базе списков строятся более сложные структуры: например, хеш-таблицы могут использовать связные списки для хранения цепочек коллизий, графы – для хранения списков смежности (список соседних вершин для каждой вершины графа). В низкоуровневых системах связные списки применяются для управления памятью. Многие языки предоставляют реализацию связного списка (например, LinkedList в Java), но в повседневном коде связные списки используются реже, чем массивы/списки, поскольку произвольный доступ важнее.

16. Что такое стек?

Стек – структура данных, работающая по принципу LIFO (Last In, First Out) – «последним пришёл, первым вышел». Это значит, что элементы добавляются и удаляются только с одного конца структуры, называемого вершиной стека. Представьте стопку тарелок: чтобы взять тарелку, вы обычно берёте верхнюю (последнюю положенную). Стек работает аналогично.

Основные операции стека:

• push – добавить элемент на вершину стека.

• pop – удалить элемент с вершины стека (и вернуть его значение).

• top (peek) – посмотреть значение верхнего элемента, не удаляя его.

Например, изначально стек пуст. Вызвали push(5) – теперь вершина содержит 5. Затем push(8) – теперь наверху 8, под ним 5. Push(3) – наверху 3 (стек: , где 3 последний добавлен). Операция pop снимет 3 (последний) и вернёт его; стек станет , вершина – 8.

Внутренняя реализация стека может быть разной: часто используют обычный массив (список) или связный список. При реализации на массиве новый элемент кладётся в конец массива, а индекс вершины увеличивается. При pop – просто уменьшается индекс вершины. На связном списке push/pop могут добавлять/удалять голову списка.

Применение стека:

• Рекурсия и вызовы функций: системный стек вызовов хранит адреса возврата и локальные переменные функций. Последняя вызванная функция завершается первой – типичное LIFO.

• Выражения и парсинг: используя стек, можно проверять корректность скобок в выражении, конвертировать инфиксную запись выражения в постфиксную, вычислять арифметические выражения.

• История действий: кнопка "Назад" в браузере – по сути стек страниц (последняя посещённая уходит первой при возврате).

• Поиск в глубину (DFS) в алгоритмах на графах можно реализовать с явным стеком (или рекурсией, что по сути тоже стек).

Стек – простая, но очень мощная структура. Во многих языках есть готовая реализация стека (например, Stack в Java, в Python роль стека выполняет обычный список с методами append()/pop()). Время выполнения операций push/pop – O(1) (амортизированное, если динамический массив – очень быстро). Главное ограничение – доступ только к верхнему элементу, но для LIFO-поведения это именно то, что нужно.

17. Что такое очередь?

Очередь – структура данных, работающая по принципу FIFO (First In, First Out) – «первым пришёл, первым вышел». Это похоже на обычную очередь в магазине: кто раньше встал, тот раньше и обслуживается. В очереди элементы добавляются в один конец (в «хвост» очереди) и извлекаются с другого конца (с «головы» очереди).

Основные операции очереди:

• enqueue – добавить элемент в конец очереди (зайти в очередь).

• dequeue – удалить элемент из начала очереди (выйти из очереди) и вернуть его.

• front (peek) – посмотреть элемент в начале очереди без удаления.

Например, изначально очередь пуста. enqueue(5) – теперь в очереди (5 и в голове, и в хвосте). enqueue(8) -> очередь (5 – голова, 8 – хвост). enqueue(3) -> . Операция dequeue уберёт первый элемент (5) – очередь станет (8 новая голова, 3 хвост), а извлечённое значение 5 возвращается.

Реализация очереди может быть на массиве или связанном списке. При использовании массива, чтобы делать эффективный dequeue, часто применяют кольцевой буфер: массив используется по кругу, с двумя индексами – head и tail. При добавлении tail смещается, при удалении – head смещается. Если доходим до конца массива, индексы циклически переходят в начало. Это позволяет использовать массив как бесконечный круговой буфер и выполнять операции за O(1). В высокоуровневых языках, таких как Python, можно использовать collections.deque – двустороннюю очередь, оптимизированную для добавления/удаления с обоих концов.

Применение очередей:

• Обработка задач в порядке поступления: например, очередь задач на принтер – документы печатаются в порядке отправки.

• Моделирование очередей ожидания: клиенты в банке, пакеты данных в сети – всё это модели очередей.

• Алгоритмы на графах – поиск в ширину (BFS): BFS использует очередь для постепенного обхода уровней графа.

• Буферы данных: при обмене данными (I/O) часто применяются очереди для сглаживания разницы скоростей (Buffer, FIFO).

Очередь, как и стек, – очень простая, но широко используемая структура. Операции enqueue/dequeue выполняются за O(1). Есть также понятие двусторонней очереди (deque), которая позволяет добавлять/удалять элементы с обоих концов – это более универсальная структура.

18. Что такое дерево (например, бинарное дерево)?

Дерево – это нелинейная структура данных, в которой элементы (называемые узлами) организованы иерархически: каждый узел может иметь дочерние узлы. Дерево похоже на перевернутое реальное дерево: есть корень (root) – исходный узел, от которого отходят ветви к другим узлам. Узлы, не имеющие потомков, называются листьями.

Одним из наиболее распространённых видов деревьев является бинарное дерево, в котором каждый узел может иметь не более двух детей: левого и правого. Бинарные деревья широко используются, особенно их разновидность – бинарные деревья поиска (Binary Search Tree, BST), где для каждого узла все элементы в левом поддереве меньше (или равны) значения этого узла, а в правом поддереве – больше (или равны). Это свойство позволяет быстро искать элементы – в среднем за O(log n) – путем спуска по дереву (сравнивая с узлами, как при двоичном поиске, только в структуре дерева).

Основные понятия дерева:

• Корень – вершина, не имеющая родительского узла (начало дерева).

• Лист – узел, у которого нет дочерних узлов.

• Высота дерева – максимальная длина пути от корня до листа (число уровней).

• Поддерево – любое дерево, состоящее из узла и всех его потомков.

Пример: рассмотрим бинарное дерево поиска, в которое добавлены числа: 8, 3, 10, 1, 6, 14, 4, 7, 13. Структура может получиться такая:

Здесь корень – 8. Листья – 1, 4, 7, 13 (и 14, если нет потомков указанных). Заметим, что для каждого узла соблюдается правило BST: слева меньше, справа больше.

Плюсы деревьев:

• Отражают иерархическую структуру данных (например, файловая система – дерево каталогов).

• Позволяют быстрый поиск, вставку и удаление (в сбалансированных деревьях ~O(log n)).

• Многие алгоритмы (поиск путей, оптимизация выражений, парсинг) естественно выражаются через деревья.

Минусы/особенности:

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

• Работа с указателями: узлы дерева чаще реализуются как объекты со ссылками на детей, что требует аккуратности (или использования готовых библиотек).

Обходы дерева:

• Обход в глубину (DFS) – может быть трёх видов: прямой (NLR: Node-Left-Right), симметричный (LNR, in-order) и обратный (LRN). Для BST симметричный обход выдаст отсортированную последовательность значений.

• Обход в ширину (BFS) – посещение узлов уровня за уровнем, часто реализуется через очередь.

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

19. Что такое граф (структура данных)?

Граф – это структура данных, состоящая из набора вершин (nodes, точки) и рёбер (edges), которые соединяют пары вершин. Граф используется для представления разнообразных связей и отношений между объектами. Формально, граф G = (V, E), где V – множество вершин, E – множество рёбер (пар вершин).

Виды графов:

• Неориентированный граф – рёбра не имеют направления (связь двусторонняя). Например, граф дружбы в соц. сети: если A дружит с B, то и B дружит с A.

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

• Взвешенный граф – рёбрам присвоены веса (например, длина дороги, стоимость перелёта между городами и т.д.). Если веса не указаны, иногда подразумевается вес 1 для всех.

• Несвязный и связный граф: граф называется связным, если из любой вершины можно добраться до любой другой по рёбрам (в неориентированном графе). В ориентированном для сильной связности требуется достижимость в обе стороны.

Граф можно представить разными способами:

• Матрица смежности: квадратная матрица размера |V|x|V|, где на пересечении (i,j) стоит отметка (например 1), если есть ребро между вершинами i и j.

• Список смежности: для каждой вершины хранится список вершин, с которыми она соединена ребром. Например, для вершины А: означает ребра A–B, A–C.

Пример графа: вершины {A, B, C, D}, рёбра: {A–B, A–C, B–D, C–D}. Можно изобразить точки A, B, C, D и соединить их линиями: A соединён с B и C, B с D, C с D. Это неориентированный граф. Если сделать стрелки, например A -> B, C -> A, B -> D, D -> C – получится ориентированный граф со своими путями.

Графы очень универсальны. Они моделируют:

• Социальные сети (люди – вершины, дружба/подписки – рёбра).

• Компьютерные сети (устройства – вершины, соединения – рёбра).

• Дороги и маршруты (города – вершины, дороги – рёбра с весами = расстояния).

• Зависимости задач (задачи – вершины, «нужно выполнить перед» – ориентированные рёбра).

• Состояния и переходы (состояния системы – вершины, переход – ребро).

Для работы с графами важны алгоритмы поиска путей, обходов:

• Поиск в глубину (DFS) и поиск в ширину (BFS) – основные способы обхода графа.

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

• Алгоритмы поиска минимального остовного дерева (например, алгоритмы Прима и Крускала) – задача найти подмножество рёбер, соединяющих все вершины при минимальной общей стоимости (актуально для задач вроде прокладки кабеля между городами).

• Алгоритмы топологической сортировки (для ориентированных ацикличных графов) – упорядочивание вершин в порядке зависимостей.

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

20. Что такое хеш-таблица?

Хеш-таблица (hash table, также называют словарём или map) – структура данных, которая хранит пары «ключ–значение» и обеспечивает очень быструю выборку по ключу, в среднем за O(1). Идея хеш-таблицы: индекс для размещения элемента вычисляется с помощью специальной функции – хеш-функции – на основе ключа.

Как это работает:

• Каждому возможному ключу сопоставляется некоторый индекс (число) посредством хеш-функции. Например, ключ "apple" хешируется в число 5, ключ "orange" – в 17 (условно).

• Внутри хеш-таблицы обычно лежит массив (называемый бакетом). Элемент с ключом "apple" будет храниться в ячейке с индексом 5 этого массива. Чтобы позже найти "apple", мы снова вычисляем хеш (получаем 5) и идём сразу в ячейку 5.

• Таким образом, поиск, вставка и удаление – при условии удачного хеширования – происходят очень быстро, без необходимости просматривать много данных.

Проблема, которая возникает, – коллизии: разные ключи могут давать один и тот же хеш. Например, "car" и "arc" могут случайно хешироваться в одно число. Решается это по-разному:

• Метод цепочек: в каждой ячейке массива хранится не один элемент, а список (связный список) элементов, чьи ключи дали один и тот же индекс. Если произошло совпадение, новый элемент добавляется в список. При поиске по ключу мы смотрим в хеш-ячейку и перебираем там список. При удачной хеш-функции списки короткие, и сложность всё ещё близка к O(1).

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

Хорошая хеш-функция должна равномерно распределять ключи по таблице, минимизируя коллизии. При достаточно редкой таблице (коэффициент заполнения < 0.7 примерно) и хорошем хешировании поиск/вставка/удаление выполняются за амортизированное O(1), т.е. очень быстро и не зависят линейно от числа элементов.

Применение хеш-таблиц:

• Ассоциативные массивы: реализация словарей, когда нужно хранить по произвольному ключу (строке, числу) какое-то значение. Например, словарь {"name": "Ivan", "age": 30} – классический пример, внутри которого хеш-таблица.

• Множества (set): можно реализовать через хеш-таблицу, храня только ключи (значение пустое) – тогда получим набор уникальных элементов, с быстрыми проверками принадлежности.

• Кеширование: хеш-таблица используется для хранения кэша (быстрый доступ по ключу к сохранённому ранее результату).

• Уникальность и подсчёты: подсчитать частоту слов в тексте удобно словарём (ключ – слово, значение – частота). Проверить, встречался ли элемент – через множество.

Хеш-таблицы повсеместно используются в программировании из-за своей скорости. Во многих языках dict или map – одна из базовых структур. Надо помнить, что в худшем случае (например, если все ключи дали один хеш) операции могут выродиться в O(n), но такое встречается редко при хорошей реализации. Также хеш-таблица не хранит элементы в упорядоченном виде (порядок ключей фактически случайный), поэтому если нужен упорядоченный вывод, надо использовать другие структуры (сбалансированные деревья, например).

21. Как работает поиск в ширину (BFS) в графах?

Поиск в ширину (BFS, Breadth-First Search) – алгоритм обхода графа, при котором мы сначала посещаем все вершины, находящиеся на расстоянии 1 ребро от стартовой, затем на расстоянии 2, 3 и т.д. Проще говоря, BFS обходится уровень за уровнем от начальной вершины.

Как BFS работает:

1. Алгоритм начинает с заданной стартовой вершины. Помещаем эту вершину в очередь.

2. Берём из очереди первую вершину (пусть это A) – посещаем её (в реальном коде обычно помечают вершину как посещённую, чтобы не зациклиться).

3. Все соседние вершины (не посещённые ранее) добавляем в очередь.

4. Повторяем: извлекаем следующую вершину из очереди, посещаем, кладём её соседей в очередь... пока очередь не опустеет или пока не найдём искомый элемент (если задача – поиск).

5. Таким образом, сначала будут посещены все вершины на расстоянии 1 от старта, потом 2, и так далее.

Пример: возьмём неориентированный граф:

Если стартовать BFS из A: сначала посетим A. Очередь = . Берём A, добавляем её соседей B и C в очередь. Теперь очередь = . Посещаем B (вторым) – его соседи: A (уже был) и D (ещё нет) -> добавляем D. Очередь = . Посещаем C (третьим) – его соседи: A (был), D (уже в очереди, отметим как запланирован) -> ничего нового. Очередь = . Посещаем D (четвёртым) – его соседи B, C уже были. Очередь пустая, конец обхода. Итоговый порядок обхода: A, B, C, D.

BFS полезен для:

• Поиска кратчайшего пути в невзвешенном графе: Если нужно найти минимальное число шагов из A в D, BFS гарантированно найдёт самый короткий путь (потому что как только D извлечётся из очереди, мы дошли до него кратчайшим путем). В примере выше кратчайший путь A->D найден через B (или C) за 2 шага.

• Обхода графа для проверки связности: BFS из одной вершины посетит всю компоненту графа.

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

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

Реализация BFS обычно использует очередь. Псевдокод:

Таким образом, происходит поуровневый обход графа. BFS гарантирует, что первый раз, когда мы видим какую-то вершину, мы пришли к ней кратчайшим путём от старта (по количеству рёбер). Это свойство часто используется.

22. Как работает поиск в глубину (DFS) в графах?

Поиск в глубину (DFS, Depth-First Search) – алгоритм обхода графа, который продвигается вглубь по одному из путей, пока возможно, а затем, при упирании в тупик, возвращается назад (backtracking) и продолжает по другому пути. Проще говоря, DFS старается идти от стартовой вершины как можно дальше, прежде чем вернуться и рассмотреть альтернативы.

Как работает DFS:

1. Начинаем с заданной стартовой вершины. Помечаем её посещённой.

2. Берём одного из её соседей, который ещё не посещён, переходим к нему (углубляемся) и также помечаем.

3. Снова берём соседа этой новой вершины, если есть непосещённый – идём дальше.

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

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

6. Процесс заканчивается, когда вернулись к старту и перебрали все альтернативные пути.

Пример (тот же граф):

DFS из A: пометим A, пойдём, скажем, в B. Пометили B, из B пойдём в его непосещённого соседа – D (А уже посещён). Пометили D. Из D соседи B и C; B уже посещён, идём в C. Пометили C. У C соседи A и D, они оба посещены – тупик. Возвращаемся к D, у D альтернативный сосед C (но он уже посещён) – D полностью обработан, возвращаемся к B. У B альтернативный сосед (кроме D) – A (но он посещён) – возвращаемся к A. У A альтернативный сосед – C, но C уже посещён. Обход закончен. Порядок посещения: A, B, D, C. Обратите внимание, что D был посещён раньше C в этом порядке (в отличие от BFS, где C раньше D). По сути мы прошли одним путём A->B->D->C, а потом откатились.

DFS обычно реализуют либо рекурсивно, либо с использованием стека. Рекурсивный псевдокод:

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

Применение DFS:

• Обнаружение путей и компонент: как и BFS, DFS может найти все вершины в компоненте связности. Он также может найти путь между двумя вершинами (не обязательно кратчайший, но какой-нибудь).

• Обход дерева: DFS по сути – это стандартный способ обхода дерева (прямой, симметричный, обратный – частные случаи DFS).

• Топологическая сортировка: DFS позволяет упорядочить вершины ориентированного ацикличного графа (DAG) в линейный порядок. Для этого используется модификация DFS с записью вершин в определённый момент (по завершении обработки узла).

• Поиск циклов: DFS можно адаптировать для обнаружения циклов в графе (если в процессе DFS пытаемся посетить вершину, которая уже находится в текущем стеке вызовов – найден цикл).

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

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

По сложности DFS также O(V + E) – надо посетить каждую вершину и каждое ребро в худшем случае. Если граф очень глубокий, рекурсивный DFS может уйти глубоко в стек, поэтому иногда применяют итеративный вариант с явным стеком. Но концептуально он проще BFS, особенно для рекурсии.

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

Динамическое программирование (Dynamic Programming, DP) – это метод оптимизации алгоритмов, суть которого в разбивании задачи на перекрывающиеся подзадачи, решении этих подзадач и сохранении их решений, чтобы каждую подзадачу решать только один раз. Фактически, динамическое программирование – способ сделать решение задачи более эффективным за счёт хранения промежуточных результатов.

Когда применяется DP:

• Задача может быть разбита на подзадачи, причём подзадачи повторяются при разных вариантах решения.

• Рекурсивное решение наивным методом приводит к экспоненциальной сложности из-за многократного решения одних и тех же подпроблем.

• Необходимо запоминать результаты подпроблем (мемоизация) или заполнять таблицу результатов итеративно (табулирование).

Классический пример – вычисление чисел Фибоначчи. Рекурсивное определение: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1. Наивный рекурсивный алгоритм вычисления F(n) будет экспоненциальным, потому что порождает кучу повторных вычислений (F(n-1) и F(n-2) в свою очередь оба вычисляют F(n-3) и так далее). Динамическое программирование предлагает хранить уже вычисленные значения F(k) в таблице. Можно либо рекурсивно с мемоизацией: вычисляя F(n), сначала проверяем, нет ли результата для n в памяти; если нет – рекурсивно вычисляем, сохраняя по пути. Либо итеративно: посчитать F(2), зная F(0), F(1); потом F(3), зная F(2) и F(1); и так до F(n). В итоге мы затратим линейное время O(n) вместо экспоненциального.

Другие примеры классических задач, решаемых DP:

• Задача о рюкзаке: мы строим таблицу оптимальных стоимостей для подсетов предметов и ёмкостей.

• Поиск наибольшей общей подпоследовательности (LCS) или расстояния Левенштейна между строками – формируем матрицу решений для префиксов строк.

• Разбиение чисел, комбинаторика – многие задачи комбинаторного подсчёта (сколькими способами можно...?) решаются динамикой.

• Оптимальные пути в решётке – например, число маршрутов в сетке или наибольшая сумма на пути – тоже удобно через DP.

Принципы динамического программирования:

1. Определить структуру подзадач: понять, из каких более мелких задач состоит исходная. Часто для DP формулируют рекуррентное соотношение.

2. Рекуррентное решение: записать решение задачи через решения подзадач.

3. Хранение результатов: завести таблицу (массив) для хранения ответов подзадач.

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

Пример: задача о рюкзаке. Пусть у нас есть массив предметов с заданными весами и ценностями, и рюкзак ёмкости W. Можно составить DP-таблицу dp – максимальная ценность, которую можно набрать из первых i предметов, не превышая вес w. Рекуррент: либо не берём i-й предмет (dp = dp), либо берём (тогда dp = dp] + value при условии что weight <= w), и берём максимум из этих двух вариантов. Заполняя такую таблицу от i=1...N и w=0...W, получаем решение за O(N*W) вместо экспоненциального перебора всех комбинаций.