Алгоритмы на Python: Подготовка к собеседованиям в российский BigTech

Введение в алгоритмические собеседования и оценка сложности (Big O)

Процесс отбора в крупные технологические компании, известные как BigTech (Яндекс, VK, Авито, Т-Банк и другие), кардинально отличается от найма в обычные студии разработки. Ключевым этапом здесь является алгоритмическое собеседование. Это строгий формат технического интервью, где кандидату предлагается решить одну или несколько нестандартных задач с использованием структур данных и алгоритмов, написав рабочий код на доске или в онлайн-редакторе без доступа к интернету и подсказкам среды разработки.

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

> Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций. > > Baikov.dev

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

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

Что такое нотация Big O

Асимптотическая сложность — это универсальный способ описания производительности функции без измерения точного времени ее выполнения в секундах. Для ее выражения используется нотация О большое (Big O notation). Она показывает, как быстро возрастает время работы алгоритма или объем потребляемой им памяти при увеличении размера входных данных.

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

Представьте, что вы написали скрипт для поиска дубликатов в базе данных пользователей. Если в базе всего 100 человек, даже самый неэффективный алгоритм отработает за доли секунды, и вы не заметите разницы. Но если база вырастет до 10 000 000 пользователей, плохой алгоритм будет выполняться несколько дней, а хороший — пару секунд. Оценка через Big O позволяет предсказать это поведение еще на этапе проектирования системы.

Основные классы алгоритмической сложности

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

| Нотация | Название | Характер роста | Пример из практики | |---|---|---|---| | | Константная | Время выполнения всегда одинаково | Получение элемента списка по индексу | | | Логарифмическая | Время растет очень медленно | Бинарный поиск в отсортированном массиве | | | Линейная | Время растет пропорционально данным | Поиск максимума в неотсортированном массиве | | | Линейно-логарифмическая | Умеренный рост | Эффективные алгоритмы сортировки (Timsort) | | | Квадратичная | Время растет стремительно | Вложенные циклы, сортировка пузырьком |

Рассмотрим самые популярные классы на конкретных примерах кода на языке Python.

Константное время

Алгоритм работает за , если количество выполняемых операций абсолютно не зависит от объема входных данных.

В этом примере интерпретатор обращается к ячейке памяти по заранее известному смещению. Если в списке items находится 10 элементов, операция займет один шаг. Если в списке 1 000 000 элементов, операция все равно займет ровно один шаг. Это самый идеальный вариант работы программы.

Логарифмическое время

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

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

При элементов линейному поиску потребуется 1 000 000 шагов, а бинарному поиску с логарифмической сложностью — всего около 20 шагов, так как .

Линейное время

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

Здесь цикл for выполнится ровно столько раз, сколько элементов передано в функцию. При массиве из 50 чисел будет выполнено 50 операций сложения. При массиве из 50 000 чисел — 50 000 операций. График роста такого алгоритма представляет собой прямую линию.

Квадратичное время

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

Если передать в эту функцию список из 10 элементов, она напечатает 100 пар (так как ). Но если передать 1000 элементов, количество операций мгновенно возрастет до 1 000 000. На собеседованиях в BigTech алгоритмы с квадратичной сложностью почти всегда просят оптимизировать, так как на реальных объемах данных они приводят к полному отказу систем.

Правила расчета Big O на собеседовании

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

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

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

Рассмотрим математический пример отбрасывания менее значимых членов: , где — размер входных данных. При малых значениях число 1000 может казаться значимым. Но при значение составит 10 000 000 000. На фоне десяти миллиардов операций слагаемые (500 000) и 1000 становятся статистической погрешностью, которая никак не влияет на общую картину производительности.

Пространственная сложность (Оценка памяти)

Помимо времени выполнения, на собеседованиях всегда оценивают пространственную сложность — объем дополнительной оперативной памяти, который требуется вашему алгоритму для работы. Она измеряется по тем же правилам и в той же нотации Big O.

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

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

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

Базовые структуры данных: массивы, строки и техника двух указателей

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

Массивы в Python: скрытая цена удобства

В языке Python роль массивов выполняют списки (list). Это динамические структуры, которые могут изменять свой размер в процессе работы программы. Под капотом они представляют собой непрерывные участки памяти, хранящие ссылки на реальные объекты.

Главная особенность динамических массивов заключается в том, как они выделяют память. Когда вы создаете пустой список, интерпретатор резервирует в памяти место «с запасом». Когда этот запас исчерпывается при добавлении новых элементов, Python выделяет новый, более крупный участок памяти, и копирует туда все старые элементы.

Из-за такого устройства памяти разные операции со списками занимают разное время:

| Операция | Синтаксис | Сложность по времени | Причина | |---|---|---|---| | Чтение по индексу | arr[i] | | Прямое вычисление адреса в памяти | | Добавление в конец | append(x) | | Запись в резервную пустую ячейку | | Вставка в начало | insert(0, x) | | Сдвиг всех существующих элементов вправо | | Удаление из начала | pop(0) | | Сдвиг всех оставшихся элементов влево | | Поиск элемента | x in arr | | Последовательный перебор всех ячеек |

Частая ошибка кандидатов на собеседованиях — использование операции pop(0) или insert(0, x) внутри цикла. Если массив содержит 100 000 элементов, вставка одного элемента в начало потребует сдвига всех 100 000 ячеек. Если сделать это 100 000 раз в цикле, программа совершит 10 000 000 000 операций, что займет несколько секунд вместо долей миллисекунды.

Строки и их неизменяемость

Строки (str) во многом похожи на массивы символов. Вы так же можете обращаться к отдельным буквам по индексу за константное время. Однако у строк есть одно критическое отличие — они неизменяемы (immutable).

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

Рассмотрим классический антипаттерн сборки текста:

Допустим, у нас есть 10 000 слов, каждое длиной 5 символов. На первой итерации создается строка из 5 символов. На второй — из 10, при этом первые 5 символов копируются заново. На третьей — из 15, и копируются уже 10 символов. К концу цикла интерпретатор выполнит сотни миллионов лишних операций копирования. Правильный подход в Python — собирать подстроки в массив (список), а затем склеивать их за один проход:

Метод двух указателей

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

> Метод двух указателей — это техника, используемая для решения различных задач на массивах и строках, при которой используются два указателя (индекса), которые перемещаются по данным по определённым правилам. > > JavaRush

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

Паттерн 1: Указатели навстречу друг другу

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

Рассмотрим классическую задачу Two Sum для отсортированного массива. Нам нужно найти два числа, которые в сумме дают заданное значение.

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

Допустим, передан массив [2, 7, 11, 15] и целевая сумма 18.

На старте left указывает на 2, right на 15. Сумма равна 17.

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

Теперь left указывает на 7, right на 15. Сумма равна 22.

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

left указывает на 7, right на 11. Сумма равна 18. Ответ найден за 3 шага.

Паттерн 2: Быстрый и медленный указатели

Второй вариант техники подразумевает, что оба указателя начинают движение с нулевого индекса, но двигаются с разной скоростью или по разным условиям. Этот подход часто применяется для модификации массива «на месте» (in-place), без выделения дополнительной памяти.

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

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

Проследим работу на массиве [0, 1, 0, 3]:

Индекс i = 0, значение 0. Условие не выполняется, идем дальше. insert_pos остается равен 0.

Индекс i = 1, значение 1. Меняем местами элементы под индексами 0 и 1. Массив становится [1, 0, 0, 3]. Увеличиваем insert_pos до 1.

Индекс i = 2, значение 0. Пропускаем.

Индекс i = 3, значение 3. Меняем местами элементы под индексами 1 и 3. Массив становится [1, 3, 0, 0].

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

Сортировки, бинарный поиск и жадные алгоритмы

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

Алгоритмы сортировки: от наивных к оптимальным

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

Самый интуитивный, но крайне неэффективный подход — это сортировка пузырьком (Bubble Sort). Алгоритм последовательно сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке habr.com. Этот процесс повторяется, пока весь массив не будет отсортирован.

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

Для массива из 10 элементов пузырьку потребуется около 100 операций. Но если элементов станет 100 000, количество операций возрастет до 10 000 000 000. В условиях BigTech такие решения недопустимы. Поэтому на практике применяются более сложные алгоритмы, основанные на парадигме «разделяй и властвуй»: быстрая сортировка (Quick Sort) и сортировка слиянием (Merge Sort).

| Алгоритм | Сложность по времени (в среднем) | Пространственная сложность | Особенность | |---|---|---|---| | Пузырьком | | | Прост в реализации, но непригоден для реальных задач | | Слиянием | | | Стабильная сортировка, но требует дополнительной памяти | | Быстрая | | | Работает быстрее на практике, сортирует «на месте» | | Timsort | | | Гибридный алгоритм, встроенный в Python по умолчанию |

В языке Python встроенная функция sorted() и метод списка sort() используют алгоритм Timsort. На собеседованиях редко просят написать сложную сортировку с нуля, но интервьюер обязательно спросит, какую асимптотическую сложность имеет встроенный метод. Правильный ответ: по времени и по памяти.

Бинарный поиск: магия логарифмического времени

Когда данные отсортированы, мы получаем мощное преимущество при поиске нужного элемента. Вместо того чтобы проверять каждую ячейку массива (что занимает линейное время ), мы можем использовать бинарный поиск (Binary Search).

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

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

Рассмотрим классическую реализацию на Python:

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

Представьте, что вы ищете конкретного пользователя в отсортированной базе из 1 000 000 записей. Обычный перебор в худшем случае потребует 1 000 000 проверок. Бинарный поиск найдет пользователя максимум за 20 шагов, так как . Разница в производительности колоссальна.

Жадные алгоритмы: локальный оптимум

Иногда задача требует не просто найти элемент, а собрать оптимальный результат из множества вариантов. Здесь на помощь приходят жадные алгоритмы (Greedy Algorithms).

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

Классический пример — задача о выдаче сдачи минимальным количеством монет. Допустим, у нас есть монеты номиналом 50, 10, 5 и 1 рубль. Нам нужно выдать сдачу в размере 66 рублей.

Берем самую крупную монету, которая не превышает остаток: 50 рублей. Осталось 16.

Снова ищем самую крупную: 10 рублей. Осталось 6.

Берем 5 рублей. Остался 1 рубль.

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

Мы выдали 4 монеты. Это и есть жадный подход. Реализация на коде выглядит лаконично:

Важно понимать главную ловушку жадных алгоритмов: они работают не всегда. Если мы изменим номиналы монет на 15, 10 и 1 рубль, а сдачу нужно выдать в размере 20 рублей, жадный алгоритм выдаст 15 + 1 + 1 + 1 + 1 + 1 (6 монет). Однако правильный ответ — 10 + 10 (всего 2 монеты).

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

Деревья, графы и хеш-таблицы

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

Хеш-таблицы: магия мгновенного доступа

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

> Хеш-таблица - это коллекция элементов, которые сохраняются таким образом, чтобы позже их было легко найти. Каждая позиция в хэш-таблице (часто называемая слотом) может содержать собственно элемент. > > Problem Solving with Algorithms and Data Structures

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

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

В языке Python коллизии разрешаются модифицированным методом открытой адресации, а сама структура встроена в язык в виде словарей (dict) и множеств (set).

| Операция | Массив (неотсортированный) | Бинарный поиск (отсортированный массив) | Хеш-таблица (в среднем) | |---|---|---|---| | Поиск | | | | | Вставка | в конец, в середину | из-за сдвига элементов | | | Удаление | | | |

Здесь — количество элементов в структуре данных.

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

Представьте массив из 100 000 чисел. Алгоритм с вложенными циклами в худшем случае совершит до 10 000 000 000 проверок. Решение через хеш-таблицу выполнит ровно 100 000 итераций, сохраняя каждое число в словарь и мгновенно проверяя наличие нужной разницы. Разница во времени выполнения составит часы против миллисекунд.

Деревья: иерархия данных

Линейные структуры отлично подходят для последовательных данных, но реальный мир часто устроен иерархично (файловые системы, структура HTML-документа). Дерево (tree) — это нелинейная структура данных, состоящая из узлов, соединенных направленными ребрами.

Каждое дерево начинается с корня (root) — самого верхнего узла. Узлы, не имеющие потомков, называются листьями (leaves). На алгоритмических секциях чаще всего встречается бинарное дерево поиска (Binary Search Tree, BST). Оно строится по строгим правилам:

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

Правое поддерево содержит ключи, которые строго больше ключа узла.

Каждое поддерево также должно быть бинарным деревом поиска.

В Python деревья не встроены в стандартную библиотеку, поэтому на собеседованиях их реализуют через пользовательские классы:

Поиск в сбалансированном бинарном дереве занимает времени, где — общее количество узлов. Если мы ищем число 42 в дереве из 1 000 000 узлов, на каждом шаге мы сравниваем искомое значение с текущим узлом. Если 42 меньше текущего значения, мы отбрасываем всю правую половину дерева и переходим влево. Таким образом, миллион элементов сокращается до одного максимум за 20 шагов.

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

Графы: моделирование связей

Если дерево — это строгая иерархия, то граф (graph) — это свободная сеть. Графы состоят из вершин (vertices) и соединяющих их ребер (edges). Социальные сети, маршруты навигаторов, интернет — всё это графы.

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

Графы классифицируются по нескольким признакам: * Направленные (ребра имеют направление, как подписки в соцсетях) и ненаправленные (связи обоюдны, как друзья). * Взвешенные (каждое ребро имеет «стоимость», например, расстояние в километрах) и невзвешенные.

Самый популярный способ представления графа в коде — список смежности (adjacency list). В Python он реализуется через хеш-таблицу (словарь), где ключом выступает вершина, а значением — список её соседей.

Для обхода графов применяются два фундаментальных алгоритма:

Поиск в ширину (Breadth-First Search, BFS). Исследует граф слоями: сначала всех ближайших соседей, затем соседей соседей. Идеально подходит для поиска кратчайшего пути в невзвешенном графе. Реализуется с помощью структуры данных «очередь».

Поиск в глубину (Depth-First Search, DFS). Идет по одной ветке до самого конца, пока не упрется в тупик, затем возвращается назад. Отлично подходит для поиска циклов и топологической сортировки. Реализуется через рекурсию или «стек».

Временная сложность обоих алгоритмов составляет , где — количество вершин, а — количество ребер.

Допустим, у нас есть граф дорог между 5 городами (), соединенных 6 трассами (). Алгоритм обхода посетит каждый город и проверит каждую трассу, совершив пропорциональное количество операций (около 11 базовых шагов). Если сеть разрастется до 10 000 городов и 50 000 дорог, алгоритм выполнит около 60 000 операций, что займет доли секунды на современном процессоре. Понимание этих структур — ключ к успешному прохождению секций по алгоритмам и системному дизайну.

Динамическое программирование и продвинутые методы решения задач

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

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

> Термин Dynamic Programming впервые использовал известный американский математик Ричард Беллман в 40-х годах XX века. Он писал, что Dynamic Programming — это способ решения сложных задач путем разбиения их на более мелкие подзадачи. > > Хабр

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

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

Перекрывающиеся подзадачи (overlapping subproblems): алгоритм многократно решает одни и те же мелкие задачи.

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

Нисходящий и восходящий подходы

Первый способ — нисходящий подход (Top-down), который использует мемоизацию (memoization). Мы пишем обычную рекурсию, но перед вычислением проверяем, нет ли уже готового ответа в специальной структуре данных (обычно в хеш-таблице).

Второй способ — восходящий подход (Bottom-up), основанный на табуляции (tabulation). Мы отказываемся от рекурсии и последовательно заполняем массив от самых маленьких подзадач к искомой.

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

| Характеристика | Нисходящий подход (Мемоизация) | Восходящий подход (Табуляция) | |---|---|---| | Направление | От сложной задачи к простым | От простых задач к сложной | | Реализация | Рекурсия + Хеш-таблица | Циклы + Массив | | Затраты памяти | Выше (из-за стека вызовов) | Ниже (нет рекурсии) | | Вычисление подзадач | Только те, что нужны по факту | Все подряд до целевой |

Преодоление ограничений жадных алгоритмов

Ранее мы рассматривали задачу о выдаче сдачи. Жадный алгоритм отлично работает для стандартных номиналов монет (например, 1, 5, 10, 50). Он всегда берет самую крупную монету. Но представим вымышленную валюту с номиналами 1, 3 и 4. Нам нужно выдать сдачу в 6 единиц.

Жадный алгоритм возьмет монету номиналом 4, останется 2. Затем он возьмет две монеты по 1. Итого: 4 + 1 + 1 (3 монеты). Однако оптимальное решение — взять две монеты по 3. Жадный подход потерпел неудачу, потому что локально оптимальный выбор (взять 4) закрыл путь к глобальному оптимуму.

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

Формула перехода состояний (уравнение Беллмана) будет выглядеть так:

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

Допустим, нам нужно набрать сумму 100 из монет [1, 5, 10, 25]. Внешний цикл пройдет 100 раз, внутренний — 4 раза для каждой суммы. Всего алгоритм совершит 400 базовых операций сравнения. Это невероятно эффективно по сравнению с полным перебором всех возможных комбинаций монет, количество которых росло бы экспоненциально.

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

Не все задачи сводятся к одномерным массивам. Часто состояние системы зависит от нескольких переменных. Классический пример — задача о рюкзаке (Knapsack problem). У нас есть набор предметов, каждый имеет вес и стоимость. Нужно максимизировать стоимость предметов в рюкзаке ограниченной вместимости.

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

Если вместимость рюкзака составляет 50 килограмм, а предметов 10, мы создаем таблицу размером 11 на 51. Алгоритм последовательно заполняет 561 ячейку, на каждом шаге принимая решение: брать текущий предмет или пропустить его. Решение базируется на уже вычисленных значениях для меньшего веса и меньшего количества предметов.

Еще один популярный класс задач на двумерное динамическое программирование — работа со строками. Например, вычисление расстояния Левенштейна (Edit Distance). Эта метрика показывает, какое минимальное количество операций (вставка, удаление или замена символа) необходимо, чтобы превратить одну строку в другую. Именно такие алгоритмы лежат в основе систем автоисправления опечаток в поисковиках и мессенджерах.

Пусть нам нужно превратить слово "кот" в слово "кит". Матрица состояний будет иметь размеры, равные длинам слов плюс один. На каждом пересечении символов алгоритм проверяет: если буквы совпадают, стоимость операции равна нулю, и мы берем значение из предыдущей диагональной ячейки. Если буквы разные, мы выбираем минимальное значение из трех соседних ячеек (соответствующих удалению, вставке и замене) и прибавляем единицу. Для слов длиной 3 символа алгоритм заполнит таблицу из 16 ячеек, мгновенно выдав минимальное количество правок.

Оптимизация памяти в динамическом программировании

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

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

Мы можем использовать всего две переменные для хранения последних значений:

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

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

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