Алгоритмы и структуры данных: Практический подход

Основы анализа сложности алгоритмов и нотация Big O

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

Зачем нам измерять сложность?

Представьте, что вы написали функцию для поиска дубликатов в списке пользователей. На вашем мощном рабочем ноутбуке с 10 тестовыми пользователями она работает мгновенно. Вы отправляете код в продакшн, где пользователей — миллион. Внезапно сервер зависает на несколько минут. Почему так произошло?

Проблема в том, что «быстро работает на моем компьютере» — это не метрика. Скорость выполнения кода в секундах зависит от множества факторов:

* Мощности процессора * Загруженности операционной системы * Языка программирования * Компилятора или интерпретатора

Нам нужен универсальный способ оценки алгоритмов, который не зависит от «железа». Нам нужно знать, как будет вести себя алгоритм при увеличении объема входных данных. Именно для этого используется Big O Notation (О-нотация).

Что такое Big O?

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

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

Представьте, что — это размер входных данных (например, количество элементов в массиве). Big O показывает зависимость количества операций от .

!Сравнение скорости роста различных алгоритмических сложностей

Давайте разберем основные виды сложности на простых примерах.

O(1) — Константная сложность

Это идеальный сценарий. Алгоритм выполняется за одно и то же время, независимо от того, сколько данных вы ему скормили — 10 элементов или 10 миллионов.

Пример из жизни: Вы берете книгу и открываете её на первой странице. Неважно, в книге 100 страниц или 1000 — действие «открыть первую страницу» занимает одинаковое время.

В программировании это часто доступ к элементу массива по индексу:

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

O(n) — Линейная сложность

Время выполнения растет прямо пропорционально количеству данных. Если данных стало в 2 раза больше, алгоритм будет работать в 2 раза дольше.

Пример из жизни: Вам нужно прочитать книгу. Если в книге 100 страниц, вы потратите 2 часа. Если 200 страниц — 4 часа.

В коде это обычно простой цикл, который проходит по всем элементам:

Если в списке items 5 элементов, цикл выполнится 5 раз. Если элементов — раз. Сложность записывается как , где — количество элементов во входных данных.

O(n²) — Квадратичная сложность

Это зона опасности. Время выполнения растет пропорционально квадрату количества элементов. Часто встречается в алгоритмах с вложенными циклами.

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

В коде это выглядит так:

Давайте посчитаем операции: * Если , мы выполним операций. * Если , мы выполним операций.

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

> Важно: Старайтесь избегать при работе с большими данными. Если , то будет равен 10 миллиардам операций, что может «повесить» ваш сервер.

O(log n) — Логарифмическая сложность

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

Пример из жизни: Поиск имени в телефонном справочнике. Вы открываете книгу посередине. Если имя на букву «К», а вы открыли на «М», вы отбрасываете вторую половину книги и ищете только в первой. Затем снова делите оставшуюся часть пополам.

Формула логарифма выглядит так:

Где — это количество входных данных, а — количество операций (шагов), необходимых для решения задачи. Это вопрос: «Сколько раз нужно разделить на 2, чтобы получить 1?».

Например, если у вас 1024 элемента (), то алгоритму потребуется всего 10 шагов, так как .

Как определять сложность: Правила упрощения

При анализе Big O нас интересует только доминирующий фактор роста. Мы отбрасываем константы и менее значимые слагаемые.

1. Отбрасывайте константы

Рассмотрим код:

Казалось бы, мы проходим по списку дважды, значит это . Но в Big O константы не важны. Разница между и ничтожна по сравнению с разницей между и . Поэтому превращается просто в .

2. Оставляйте только старшую степень

Пусть время работы вашего алгоритма описывается формулой:

Где — общее время выполнения, — квадратичная часть, — линейная часть, а — константная часть.

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

* *

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

Пространственная сложность (Space Complexity)

До сих пор мы говорили о времени (Time Complexity). Но память компьютера тоже не бесконечна. Space Complexity показывает, сколько дополнительной памяти требует алгоритм.

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

!Визуализация потребления памяти различными алгоритмами

Худший, средний и лучший случаи

Обычно, когда говорят о Big O, имеют в виду худший случай (Worst Case).

Представьте, что вы ищете число в массиве. * Лучший случай: Число находится первым. Сложность . * Худший случай: Число находится последним или его вообще нет. Сложность .

Мы ориентируемся на худший случай, чтобы гарантировать, что наша программа не «упадет» даже при самых неудачных данных.

Резюме

Big O измеряет рост сложности алгоритма, а не время в секундах.

— мгновенно, — очень быстро, — нормально, — медленно.

Мы отбрасываем константы: — это .

Мы учитываем не только время процессора, но и потребляемую память.

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

Линейные структуры данных: массивы, связные списки и хеш-таблицы

В предыдущей лекции мы освоили нотацию Big O — универсальный язык для измерения эффективности кода. Мы научились отличать мгновенные алгоритмы () от медленных (). Но алгоритмы не существуют в вакууме. Они работают с данными.

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

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

Массивы (Arrays): Фундамент памяти

Массив — это самая базовая структура данных. Когда вы объявляете массив, компьютер выделяет непрерывный блок памяти определенного размера.

Представьте себе улицу с одноэтажными домами, стоящими вплотную друг к другу. У каждого дома есть номер: 0, 1, 2, 3 и так далее. Это и есть массив. Дома — это ячейки памяти, а номера домов — это индексы.

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

Почему доступ по индексу такой быстрый?

Вы наверняка слышали, что получение элемента массива по индексу (например, arr[5]) имеет сложность . Но почему? Компьютер не перебирает элементы один за другим. Он использует простую математику.

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

Где: * — искомый адрес ячейки в памяти. * — адрес начала массива (где стоит «нулевой дом»). * — номер элемента, который нам нужен. * — размер одного элемента в байтах (например, целое число обычно занимает 4 или 8 байт).

Благодаря этой формуле, доступ к 1-му элементу и к 10-миллионному элементу занимает абсолютно одинаковое время.

Проблема вставки и удаления

Если чтение — это суперсила массивов, то изменение размера — их криптонит.

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

Если в массиве элементов, и вы вставляете данные в самое начало, вам придется переместить все элементов. Следовательно, сложность вставки в худшем случае — .

Плюсы массивов: * Мгновенный доступ к данным по индексу — . * Эффективное использование памяти (нет накладных расходов).

Минусы массивов: * Медленная вставка и удаление элементов из середины или начала — . * В классических языках (C, Java) размер массива фиксирован. Если место кончилось, нужно создавать новый массив большего размера и копировать туда все данные.

Связные списки (Linked Lists): Гибкость против скорости

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

В отличие от массива, элементы связного списка могут быть разбросаны по памяти где угодно. Нет никакого «соседства». Как же они находят друг друга?

Каждый элемент (назовем его Узел или Node) хранит две вещи:

Собственно данные (значение).

Ссылку (указатель) на следующий узел.

Это похоже на квест «поиск сокровищ». Вы находите записку (первый узел), в ней написано: «Иди к старому дубу». Вы идете к дубу (второй узел), там записка: «Ищи под камнем». Вы не знаете, где находится пятый этап квеста, пока не пройдете четвертый.

!Структура односвязного списка: узлы, связанные указателями.

В коде это выглядит примерно так:

Сложность операций

1. Доступ к элементу: Чтобы получить 5-й элемент, мы не можем использовать формулу, как в массиве. Мы обязаны начать с головы (Head) и пройти по цепочке ссылок 5 раз. Сложность доступа: .

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

Виды связных списков

* Односвязный (Singly Linked List): Ссылки идут только вперед. Нельзя вернуться назад. * Двусвязный (Doubly Linked List): Каждый узел имеет ссылку и на следующий (next), и на предыдущий (prev) элемент. Это удобнее, но требует больше памяти.

Плюсы связных списков: * Быстрая вставка и удаление (при наличии указателя на нужную позицию). * Динамический размер: память выделяется по мере необходимости.

Минусы связных списков: * Медленный доступ к случайному элементу — . * Дополнительный расход памяти на хранение ссылок.

Хеш-таблицы (Hash Tables): Магия

А теперь представьте структуру данных, которая объединяет лучшее из двух миров: она позволяет вставлять, удалять и искать данные за . Звучит как магия? Это хеш-таблица (в Python это dict, в JavaScript — Object или Map, в Java — HashMap).

Хеш-таблица хранит данные в формате Ключ-Значение (Key-Value).

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

В основе лежит массив. Но мы не используем индексы 0, 1, 2 напрямую. Мы используем хеш-функцию.

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

Процесс выглядит так:

Вы даете системе ключ (например, имя пользователя "Alice").

Хеш-функция превращает строку "Alice" в число (индекс массива), например, 492.

Данные сохраняются в ячейку массива под индексом 492.

Когда вы хотите найти данные по ключу "Alice":

Хеш-функция снова превращает "Alice" в 492.

Система мгновенно забирает данные из ячейки 492.

!Преобразование ключа в индекс массива через хеш-функцию.

Коллизии

Мир не идеален. Иногда хеш-функция может выдать одинаковый индекс для разных ключей. Например, и "Alice", и "Bob" могут получить индекс 5. Это называется коллизия.

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

> При плохой хеш-функции или переполненной таблице хеш-таблица может деградировать до связного списка, и скорость упадет до .

Однако в среднем случае (Average Case) сложность операций остается .

Сводная таблица производительности

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

| Структура данных | Доступ (Access) | Поиск (Search) | Вставка (Insertion) | Удаление (Deletion) | | :--- | :--- | :--- | :--- | :--- | | Массив | | | | | | Связный список | | | | | | Хеш-таблица | N/A | | | |

\ Для связного списка вставка/удаление возможны, только если у нас уже есть ссылка на нужный узел (или предыдущий к нему).*

Когда и что использовать?

Используйте массивы, когда:

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

Используйте связные списки, когда:

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

Используйте хеш-таблицы, когда:

* Вам нужно быстро искать данные по ключу (например, поиск пользователя по ID, поиск товара по артикулу). * Это ваш выбор «по умолчанию» для большинства задач поиска.

Заключение

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

В следующей статье мы поднимемся на уровень выше и изучим структуры данных, которые диктуют свои правила поведения: Стеки и Очереди. Вы узнаете, как работает кнопка «Назад» в браузере и как принтер выстраивает документы на печать.

Алгоритмы сортировки, бинарный поиск и метод двух указателей

В предыдущих лекциях мы заложили фундамент: разобрались с Big O и изучили, как данные хранятся в памяти (массивы, списки, хеш-таблицы). Теперь пришло время заставить эти данные работать.

Представьте, что у вас есть телефонная книга, в которой имена записаны в случайном порядке. Найти номер «Алексея» в такой книге — задача невыполнимая за разумное время. Вам придется читать каждую строчку подряд. Но если книга отсортирована по алфавиту, вы найдете нужное имя за секунды.

Сегодня мы разберем три важнейших инструмента в арсенале разработчика:

Сортировка — организация хаоса.

Бинарный поиск — молниеносное нахождение данных.

Метод двух указателей — элегантный паттерн для работы с массивами.

Алгоритмы сортировки: от простого к эффективному

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

Пузырьковая сортировка (Bubble Sort)

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

Идея: Мы проходим по массиву слева направо, сравниваем два соседних элемента и, если они стоят в неправильном порядке, меняем их местами. Мы повторяем этот проход до тех пор, пока массив не станет отсортированным.

!Визуализация процесса «всплытия» самого большого элемента в конец массива.

Посмотрим на код:

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

Формула сложности:

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

Сложность означает, что если количество данных увеличится в 10 раз, время сортировки увеличится в 100 раз. Для массива из 100 000 элементов пузырьковая сортировка может занять несколько минут или даже часов.

Эффективные сортировки (Merge Sort, Quick Sort)

В реальной жизни (например, когда вы вызываете .sort() в Python или Java), используются более умные алгоритмы, такие как Быстрая сортировка (Quick Sort) или Сортировка слиянием (Merge Sort).

Они используют принцип «Разделяй и властвуй». Вместо того чтобы сравнивать всё со всем, они разбивают массив на мелкие части, сортируют их по отдельности, а затем объединяют.

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

Где — количество элементов, а — логарифм от количества элементов.

Почему это круто? * Для : * (триллион операций). * (двадцать миллионов операций).

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

Бинарный поиск: Ищем иголку в стоге сена

Теперь, когда наши данные отсортированы, мы можем использовать Бинарный поиск (Binary Search). Это тот самый алгоритм, который позволяет найти запись в базе данных из миллиарда пользователей за доли миллисекунды.

Главное условие: Массив обязательно должен быть отсортирован.

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

Вспомните игру «Угадай число». Я загадал число от 1 до 100. Вы называете число, а я говорю «больше» или «меньше».

* Плохая стратегия: 1? 2? 3? ... 99? (Линейный поиск, ). * Хорошая стратегия: 50? * Я говорю: «Больше». * Вы сразу отбрасываете числа от 1 до 50. Осталось 50-100. Вы называете 75.

Каждым шагом вы отсекаете ровно половину вариантов.

!Схематичное изображение процесса деления области поиска пополам.

Реализация в коде

Математика эффективности

Сколько раз нужно разделить число на 2, чтобы получить 1? Это и есть определение логарифма по основанию 2.

Сложность бинарного поиска:

Где — размер массива, а — количество шагов алгоритма.

Пример: * Если , нужно около 7 шагов (). * Если (все люди в интернете), нужно всего 32 шага ().

Именно поэтому бинарный поиск считается одним из самых быстрых алгоритмов в истории.

Метод двух указателей (Two Pointers)

Это не отдельный алгоритм, а паттерн (шаблон) решения задач, который часто встречается на собеседованиях в Google, Facebook и Amazon. Он позволяет превратить медленные решения в быстрые .

Задача: Сумма двух чисел

Дано: Отсортированный массив чисел. Нужно найти два числа, которые в сумме дают заданное число .

Пример: arr = [-3, 2, 3, 4, 9], target = 6.

Наивное решение: Перебрать каждую пару чисел с помощью двух циклов. Сложность: . Слишком медленно.

Решение с двумя указателями: Мы ставим один указатель (left) на начало массива, а второй (right) — на конец.

Считаем сумму: arr[left] + arr[right].

Если сумма равна цели — победа!

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

Если сумма меньше цели, нам нужно увеличить сумму. Мы сдвигаем левый указатель вправо (left + 1), чтобы взять число побольше.

!Визуализация движения двух указателей от краев к центру массива.

Код решения

Почему это работает быстро?

В этом алгоритме каждый указатель двигается только в одну сторону. Мы проходим по массиву всего один раз.

Сложность:

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

Резюме

Сортировка — это база. Пузырьковая сортировка () годится только для обучения. В реальности используйте встроенные сортировки ().

Бинарный поиск позволяет искать данные в отсортированном массиве за . Это невероятно быстро даже для миллиардов записей.

Метод двух указателей — мощная техника оптимизации задач на массивах, позволяющая решать их за один проход .

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

Нелинейные структуры: деревья, графы и алгоритмы обхода (BFS/DFS)

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

Но реальный мир устроен сложнее. Как представить структуру папок на вашем компьютере? Как описать связи между друзьями в социальной сети? Как навигатор строит маршрут из точки А в точку Б?

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

Деревья (Trees): Иерархия во всем

Дерево — это структура данных, которая имитирует иерархию. В программировании деревья растут корнем вверх.

Представьте генеалогическое древо или схему управления в крупной корпорации. Есть один главный начальник (Корень), у него есть заместители, у тех — свои подчиненные, и так до самых рядовых сотрудников.

!Структура дерева с корнем вверху и листьями внизу.

Основные термины:

* Корень (Root): Самый верхний узел, с которого все начинается. У него нет родителей. * Узел (Node): Любой элемент дерева, содержащий данные. * Ребро (Edge): Связь (линия) между двумя узлами. * Лист (Leaf): Узел, у которого нет потомков (детей). Тупик ветки.

Самый популярный вид деревьев в алгоритмах — Бинарное дерево. В нем у каждого узла может быть не более двух детей: левый и правый. Именно на бинарных деревьях построены многие эффективные алгоритмы поиска.

Графы (Graphs): Паутина связей

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

Граф — это набор вершин (узлов) и связей между ними. Это самая универсальная структура данных.

Примеры графов: * Социальная сеть: Люди — это вершины, дружба — это связи. * Карта метро: Станции — вершины, перегоны — связи. * Интернет: Сайты — вершины, гиперссылки — связи.

!Граф, демонстрирующий сложные связи между узлами без единого корня.

Виды графов:

Направленный (Directed): Связи имеют направление (стрелочки). Например, в Twitter вы можете читать Илона Маска, но он не читает вас. Связь односторонняя.

Ненаправленный (Undirected): Связь работает в обе стороны. Например, дружба в Facebook: если вы друзья, то это взаимно.

Взвешенный (Weighted): У каждой связи есть «вес» (стоимость). Например, расстояние между городами в километрах.

Как хранить граф в коде?

Мы не можем просто положить граф в массив. Обычно используют два способа:

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

Список смежности (Adjacency List): Для каждой вершины мы храним список соседей. Это самый популярный способ.

Пример списка смежности на Python (используем словарь):

Алгоритмы обхода: Как не заблудиться в лабиринте

Иметь структуру данных мало, нужно уметь по ней ходить. Представьте, что вы находитесь в лабиринте (графе) и ищете выход. Есть две фундаментальные стратегии поиска: BFS и DFS.

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

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

Принцип: Мы исследуем соседей текущей вершины, потом соседей соседей, и так далее. Мы двигаемся слоями.

Инструмент: Очередь (Queue) — принцип «Первый вошел, первый вышел» (FIFO).

Зачем нужен: Идеален для поиска кратчайшего пути в невзвешенном графе. Если вы ищете ближайшего к вам таксиста или минимальное количество рукопожатий до знаменитости — это BFS.

!Поиск в ширину исследует граф слой за слоем.

Реализация BFS:

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

Это стратегия «смелого исследователя». Вы идете по коридору лабиринта так далеко, как только можете. Если уперлись в тупик — возвращаетесь назад до ближайшей развилки и идете в другую сторону.

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

Инструмент: Стек (Stack) — принцип «Последний вошел, первый вышел» (LIFO) или Рекурсия (которая под капотом использует стек вызовов).

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

!Поиск в глубину уходит максимально далеко по одной ветке перед возвратом.

Реализация DFS (рекурсивно):

Сложность алгоритмов обхода

И BFS, и DFS посещают каждую вершину и проходят по каждому ребру (связи) не более определенного количества раз.

Их временная сложность описывается формулой:

Где: * (Vertices) — количество вершин в графе. * (Edges) — количество ребер (связей) в графе.

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

Итог: Что выбрать?

| Характеристика | BFS (Ширина) | DFS (Глубина) | | :--- | :--- | :--- | | Структура данных | Очередь (Queue) | Стек (Stack) / Рекурсия | | Поиск кратчайшего пути | Да (в невзвешенном графе) | Нет (может найти длинный путь) | | Потребление памяти | Много (хранит весь уровень) | Мало (хранит только текущий путь) | | Аналогия | Волна на воде | Змея в лабиринте |

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

Введение в динамическое программирование и жадные алгоритмы

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

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

Для решения таких задач существуют два мощных подхода: Жадные алгоритмы и Динамическое программирование. Сегодня мы разберемся, как они работают, в чем их различие и почему «жадность» не всегда окупается.

Жадные алгоритмы (Greedy Algorithms)

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

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

Пример: Задача о выдаче сдачи

Представьте, что вы работаете кассиром. Вам нужно выдать сдачу в 67 рублей, используя минимальное количество монет. Доступные номиналы: 1, 5, 10, 25 рублей (стандартная американская система, для примера).

Жадная стратегия:

Берем самую крупную монету, которая меньше или равна остатку.

Повторяем, пока не наберем сумму.

Процесс:

Остаток 67. Берем 25. (Осталось 42)

Остаток 42. Берем 25. (Осталось 17)

Остаток 17. Берем 10. (Осталось 7)

Остаток 7. Берем 5. (Осталось 2)

Остаток 2. Берем 1. (Осталось 1)

Остаток 1. Берем 1. (Осталось 0)

Итог: 6 монет (25, 25, 10, 5, 1, 1). Это действительно оптимальное решение для данного набора монет.

Когда жадность не работает?

Жадные алгоритмы быстры и просты в реализации. Но у них есть фатальный недостаток: они не видят «большой картины».

Изменим условия. Допустим, у нас есть монеты номиналом 1, 3 и 4 рубля. Нам нужно набрать сумму 6 рублей.

Жадный подход:

Берем максимум: 4 рубля. (Осталось 2)

Берем максимум из оставшегося: 1 рубль. (Осталось 1)

Берем 1 рубль. (Осталось 0)

Результат жадного алгоритма: 3 монеты (4 + 1 + 1).

Оптимальное решение: Взять две монеты по 3 рубля (3 + 3 = 6).

Результат: 2 монеты.

Жадный алгоритм ошибся! Он «пожадничал» на первом шаге, взяв четверку, и тем самым отрезал путь к идеальному решению.

> Жадные алгоритмы работают только тогда, когда задача обладает свойством жадного выбора (Greedy Choice Property). Это значит, что локально лучшее решение всегда ведет к глобально лучшему. Примеры: алгоритм Дейкстры (поиск пути), сжатие Хаффмана.

Динамическое программирование (Dynamic Programming)

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

Суть метода заключается в двух принципах:

Разбиение задачи: Сложная задача разбивается на более простые подзадачи.

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

Проблема чисел Фибоначчи

Классический пример. Числа Фибоначчи — это последовательность, где каждое число равно сумме двух предыдущих:

Где — искомое число, — предыдущее число, а — число перед предыдущим.

Попробуем решить это простой рекурсией на Python:

Что здесь плохого? Давайте посмотрим на дерево вызовов для fib(5).

!Дерево рекурсивных вызовов, показывающее дублирование вычислений

Мы вычисляем fib(3) два раза, fib(2) — три раза. Чем больше , тем катастрофичнее ситуация. Сложность этого алгоритма:

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

Решение через Динамическое Программирование

DP предлагает простое решение: давайте записывать ответы.

#### Подход 1: Сверху-вниз (Top-Down) с мемоизацией

Мы оставляем рекурсию, но добавляем «блокнот» (хеш-таблицу или массив), куда записываем уже вычисленные значения.

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

#### Подход 2: Снизу-вверх (Bottom-Up) или Табуляция

Зачем нам вообще рекурсия? Мы можем начать с малых чисел и дойти до нужного.

Мы заполняем таблицу слева направо. Никаких переполнений стека вызовов, максимальная эффективность.

!Процесс заполнения массива методом Bottom-Up

Возвращаемся к монетам: DP в действии

Вспомним задачу, где жадный алгоритм провалился: монеты [1, 3, 4], сумма 6.

Как решит это DP? Мы построим массив dp, где индекс — это сумма, а значение — минимальное количество монет для этой суммы.

Мы хотим найти dp[6]. Начнем с 0.

* dp[0] = 0 (0 монет для суммы 0). * dp[1]: берем монету 1. dp[1] = dp[0] + 1 = 1. * dp[2]: берем монету 1. dp[2] = dp[1] + 1 = 2 (1+1). * dp[3]: * Если берем монету 1: dp[2] + 1 = 3. * Если берем монету 3: dp[0] + 1 = 1. * Минимум: 1. * ... * dp[6]: * Если последняя монета 1: dp[5] + 1. * Если последняя монета 3: dp[3] + 1 (а dp[3] у нас 1, итого 2). * Если последняя монета 4: dp[2] + 1 (а dp[2] у нас 2, итого 3). * Минимум: 2 (это вариант 3+3).

Алгоритм гарантированно нашел оптимальное решение, перебрав варианты, но сделав это эффективно.

Сравнение подходов

| Характеристика | Жадные алгоритмы | Динамическое программирование | | :--- | :--- | :--- | | Принцип | Локально оптимальный выбор на каждом шаге | Разбиение на подзадачи + запоминание результатов | | Скорость | Очень быстро | Медленнее, так как рассматривает больше вариантов | | Гарантия оптимума | Нет (только в специальных задачах) | Да (всегда находит лучшее решение) | | Сложность реализации | Низкая | Средняя / Высокая |

Когда использовать DP?

Чтобы понять, что задачу нужно решать через DP, ищите два признака:

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

Перекрывающиеся подзадачи (Overlapping Subproblems): В процессе решения одни и те же подзадачи возникают многократно (как вычисление fib(3) в примере выше).

Заключение

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

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