Алгоритмы под капотом Python: от Big O до графов

freeCodeCamp.org 61,8 тыс. 2 ч 25 мин 35 мин 18.11.2026
Главное

Чтобы добавить миллион элементов в список Python, памяти приходится перераспределяться всего 87 раз, а бинарный поиск через модуль bisect ускоряет работу программы в 28 000 раз по сравнению с обычным перебором. Джавид Бодуров разбирает механику фундаментальных структур данных и алгоритмов «под капотом» Python — от устройства динамических массивов и хеш-таблиц до графов, мемоизации и гибридной сортировки Timsort. Этот гид систематизирует ключевые паттерны решения задач и показывает, как превратить сухой анализ сложности Big O в главный инструмент на технических интервью.

🧱 Основы алгоритмической сложности и базовые структуры данных 0:00

Анализ сложности алгоритмов и нотация Big O 2:55

Преподаватель курса Джавид Бодуров (Javid Bodurov) подчеркивает, что сравнение скорости работы программ по физическому времени в секундах бессмысленно: один и тот же скрипт может быстро выполниться на ноутбуке и зависнуть на телефоне . Единственный объективный критерий эффективности — зависимость количества базовых шагов от размера входных данных, которую описывает нотация Big O .

Джавид выделяет шесть основных категорий временной сложности, деля их на «хорошие» и «опасные»:

Для наглядности Бодуров сопоставляет все шесть типов на массиве из 1000 элементов: если константный алгоритм сделает 1 шаг, то квадратичный выполнит 1 000 000, а экспоненциальный выдаст число с более чем 300 знаками .

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

  1. Отбрасывание констант: алгоритм, делающий $2n$ операций или содержащий три последовательных цикла по $n$, все равно признается $O(n)$, так как форма графика остается линейной .
  2. Учет только старшего слагаемого: в выражении $n^2 + n$ младшая часть для 1000 элементов составляет всего 1000 против 1 миллиона, поэтому итоговая сложность записывается как $O(n^2)$ .
  3. Ориентация на худший случай: гарантия выполнения строится на сценарии, когда искомый элемент находится в самом конце или отсутствует вовсе .

Устройство памяти и работа массивов в Python 10:29

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

Благодаря этому компьютер мгновенно находит любой элемент по формуле: базовый_адрес + (индекс × размер_ячейки) . Переход к индексу 500 000 не требует сканирования предыдущих значений — процессор выполняет одно умножение, одно сложение и сразу обращается к нужному байту, обеспечивая сложность $O(1)$ .

Однако список в Python (list) устроен сложнее классического массива: ячейки хранят не сами объекты, а 8-байтовые указатели (ссылки) на них в 64-битной системе . Пустой список занимает 56 байт, а список из 10 элементов — 136 байт (ровно по 8 байт на указатель) . Это позволяет хранить в одной структуре разнородные типы данных .

Динамическое расширение списка Python оптимизировано: память выделяется блоками с запасом (capacity) . При добавлении элементов пустой список резервирует 4 ячейки, после 5-го элемента емкость скачет до 8, затем до 16, 24, 32, 40, 52, 64 и 76 ячеек . На 1000 операций .append() реальное перераспределение памяти происходит всего 29 раз, а на 1 миллион — лишь 87 раз . За счет этого амортизированная сложность добавления в конец составляет $O(1)$ .

Цена операций кардинально зависит от точки вмешательства:

Односвязные и двусвязные списки 19:20

Главным ограничением динамических массивов остается дороговизна вставки в середину и начало . Связный список решает эту проблему за счет отказа от непрерывного хранения данных: каждый элемент (узел/node) может располагаться в любом свободном секторе памяти . Узел состоит всего из двух полей: полезной нагрузки (value) и указателя на следующий элемент (next) .

Входом в такую цепочку служит указатель head (голова) . Платой за фрагментированное размещение становится потеря быстрого доступа по индексу: чтобы прочитать значение на позиции 500 000, программе приходится выполнить ровно 500 000 переходов по ссылкам, что снижает скорость произвольного доступа до $O(n)$ , .

Суперсила связного списка раскрывается при мутациях структуры :

Единственный подвох кроется в поиске точки изменения: чтобы удалить или вставить элемент, до него нужно дойти от головы за $O(n)$ . Для эффективной работы с концом списка вводится дополнительный указатель tail (хвост), снижающий сложность вставки в конец до $O(1)$ . Тем не менее односвязный список позволяет двигаться только в одном направлении, что создает предпосылки для внедрения двусвязных структур .

🥞 Стеки, очереди и хеш-таблицы: базовые кирпичики быстрых программ 27:16

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

Стеки, принцип LIFO и механизм стека вызовов 27:16

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

У стека выделяют три базовые операции :

В Python для создания стека не требуется писать отдельный класс: стандартный список (list) уже идеально выполняет эту роль . Метод append() выступает в роли операции push , чтение по индексу [-1] реализует peek , а встроенный метод pop() извлекает последний добавленный элемент . Если попытаться вызвать pop() на пустом списке, интерпретатор выбросит ошибку IndexError . Поскольку операции затрагивают только конец списка и элементы не сдвигаются в памяти, операции push, pop и peek выполняются за константное время $O(1)$ .

На практике со стеками разработчик сталкивается постоянно:

  1. Кнопка отмены действий (Undo): каждое изменение в текстовом редакторе отправляется на вершину стека, а при нажатии Ctrl+Z последняя правка снимается со стека и аннулируется .
  2. Кнопка «Назад» в веб-браузере: посещенные страницы сохраняются в стеке, и при возврате текущая вкладка снимается, открывая предыдущую .
  3. Стек вызовов функций (Call Stack): когда функция вызывает другую функцию, Python размещает новый стековый кадр (frame) на вершине стека . В нем сохраняются локальные переменные и адрес возврата . Когда функция завершается, ее кадр удаляется .

Если функция бесконечно вызывает саму себя, стек заполняет выделенную память . Джавид Бодуров подчеркивает, что в Python существует строгий лимит глубины рекурсии по умолчанию — 1000 фреймов . Превышение этого порога вызывает аварийную остановку программы с ошибкой RecursionError: maximum recursion depth exceeded, известную в индустрии как переполнение стека (Stack Overflow) .

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

Очереди, принцип FIFO и алгоритм поиска в ширину 34:58

Если стек переворачивает порядок поступления элементов, то очередь (Queue) работает с точностью до наоборот . Классическая аналогия — очередь за кофе: человек, вставший в очередь первым, первым получает свой напиток и покидает заведение . Новые участники встают в хвост (back), а обслуживание идет с начала (front) . Модель называется FIFO — First In, First Out («первым пришел — первым ушел») . Основные операции очереди включают добавление в конец (enqueue), удаление из начала (dequeue) и просмотр первого элемента (peek) .

Использование обычного списка Python для реализации очереди скрывает опасную алгоритмическую ловушку . Добавление в конец списка через append() работает быстро, но удаление первого элемента через pop(0) вынуждает процессор сдвигать абсолютно все оставшиеся элементы на одну ячейку влево .

Джавид Бодуров наглядно продемонстрировал это с помощью бенчмарка: удаление 1000 элементов из начала списка размером в 1 миллион элементов заняло около 0,4 секунды, демонстрируя неэффективную сложность $O(n)$ на операцию . Решением служит двусторонняя очередь deque из стандартного модуля collections . Удаление из начала с помощью метода popleft() на той же выборке в 1 миллион элементов заняло менее десятой доли миллисекунды — операция в collections.deque работает за константное время $O(1)$, что в тысячи раз быстрее обычного списка .

Очереди незаменимы в задачах распределения ресурсов:

На базе очереди реализуется фундаментальный алгоритм обхода — поиск в ширину (Breadth-First Search, BFS), находящий кратчайший путь . В качестве примера Бодуров строит лабиринт размером 5×5 клеток со стартовой точкой S и выходом E . Поиск в ширину исследует пространство концентрическими кольцами, наподобие кругов на воде: сначала клетки на расстоянии 1 шаг, затем 2, затем 3 .

Поскольку очередь отдает узлы строго в порядке добавления, ближайшие к старту клетки обрабатываются первыми, что гарантирует: первый найденный путь до выхода будет самым коротким . Во избежание бесконечного зацикливания между ячейками алгоритм фиксирует пройденные координаты во множестве seen . В тестовом лабиринте алгоритм нашел выход за 8 шагов, обработав 14 клеток , а общая временная сложность BFS составила $O(n)$ от числа доступных ячеек .

Хеш-таблицы, разрешение коллизий и внутренности словарей 42:25

Поиск элемента в неотсортированном массиве требует последовательного перебора всех элементов за линейное время $O(n)$ . В бенчмарке Бодурова проверка наличия числа в списке из 1 миллиона значений через оператор in заняла около 10 миллисекунд . Хеш-таблица решает эту проблему, предлагая поиск, вставку и удаление за константное время $O(1)$ вне зависимости от того, хранится ли в ней 10 записей или 1 миллион .

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

Для демонстрации принципа Бодуров создает простейшую хеш-функцию, суммирующую числовые коды букв слова и берущую остаток от деления на 8 :

Неизбежная проблема хеш-таблиц — коллизии, когда два совершенно разных ключа претендуют на один и тот же индекс . Например, анаграммы «melon» и «lemon» имеют идентичную сумму кодов букв (539) и обе претендуют на 3-ю ячейку . Для разрешения подобных конфликтов используются две стратегии:

  1. Метод цепочек (Chaining): каждая ячейка таблицы содержит не одиночный элемент, а связный список пар «ключ-значение» . При возникновении коллизии элемент просто дописывается в конец списка соответствующей ячейки .
  2. Открытая адресация (Open Addressing): если целевая ячейка занята, алгоритм последовательно проверяет соседние ячейки (шаг вправо), пока не найдет свободное место . Именно оптимизированный вариант открытой адресации лежит в основе встроенных словарей (dict) в Python . При удалении из таких таблиц ячейки помечаются специальным маркером, чтобы цепочка поиска последующих элементов не разрывалась на пустом месте .

Если хеш-функция распределяет ключи неравномерно и они скапливаются в одной корзине, сложность поиска деградирует до худшего сценария — $O(n)$ . Критическим параметром эффективности выступает коэффициент заполнения (Load Factor) — отношение числа сохраненных элементов к общему числу ячеек массива .

Как только коэффициент заполнения превышает порог 0,75, таблица инициирует динамическое масштабирование (resize): выделяется массив вдвое большего размера, и все существующие ключи перехешируются заново . Хотя отдельная процедура расширения таблицы является ресурсоемкой, происходит она редко, сохраняя амортизированную сложность вставок на уровне $O(1)$ .

🌳 Иерархические структуры: бинарные деревья и деревья поиска (BST) 56:09

Анатомия дерева и четыре способа обхода: от рекурсии к очереди 56:09

Завершив разбор плоских структур данных и хеш-таблиц, Джавид Бодуров подчеркивает, что реальный мир устроен иерархически . Папки на жестком диске содержат подпапки и файлы , веб-страницы строятся вокруг дерева DOM с тегами body, меню и ссылками , а корпоративные и семейные структуры ветвятся от предков к потомкам . Базовой единицей дерева выступает узел: вершина на самом верху именуется корнем (root), каждый нижележащий узел имеет строго одного родителя, элементы без потомков называются листьями (leaves), а узлы с общим родителем — соседями (siblings) . Расстояние от корня до конкретного узла задает его глубину, тогда как общее число уровней от корня до самого глубокого листа определяет высоту всего дерева .

Наиболее популярной разновидностью выступает бинарное дерево, где узел содержит не более двух потомков — левого и правого . В Python такая структура реализуется элементарным классом Node, сохраняющим значение value и два указателя left и right, которые при инициализации равны None . Сконструировав тестовое дерево из пяти элементов на трех уровнях (корень 1, левый потомок 2 с детьми 4 и 5, правый потомок 3) , Бодуров переходит к фундаментальной задаче — обходу всех вершин (traversal) . Для этого существует четыре классических алгоритма, три из которых опираются на рекурсию :

Каждый из четырех способов гарантированно посещает каждый узел ровно один раз, что дает временную сложность $O(n)$ . Тот же рекурсивный паттерн позволяет вычислить базовые метрики: высота дерева рассчитывается как единица плюс максимум из высот левого и правого поддеревьев, а суммарное число узлов — как единица плюс сумма узлов обоих поддеревьев . Для тестовой структуры функции выдали высоту 3 и размер 5 узлов .

Двоичные деревья поиска: правила упорядочивания, вставка и три сценария удаления 1:00:53

Бинарное дерево поиска (Binary Search Tree, BST) вводит строгое математическое правило: для каждого узла все значения в левом поддереве строго меньше его ключа, а в правом — строго больше . Это свойство кардинально ускоряет выборку: разыскивая число 60 в дереве с корнем 50, алгоритм сравнивает значения и отбрасывает всю левую ветвь . Перейдя в правый узел со значением 70, он делает шаг влево и сразу находит 60 — потребовалось всего 3 шага вместо перебора 7 элементов . Каждый шаг отсекает ровно половину оставшихся вариантов, воспроизводя логику бинарного поиска .

Вставка нового элемента зеркально повторяет этот путь . Небольшая рекурсивная функция спускается по ветвям: если переданный узел пуст (None), создается новая вершина; если добавляемое число меньше, вызов уходит влево, а если больше — вправо . Построив BST последовательным добавлением ключей 50, 30, 70, 20, 40, 60 и 80, Бодуров применяет к нему центрированный обход (in-order) и получает цепочку 20, 30, 40, 50, 60, 70, 80 . Центрированный обход BST всегда возвращает отсортированный массив — ключевое свойство этой структуры данных . Поиск отсутствующего значения 65 также занял всего три сравнения перед возвратом статуса «не найдено» .

Удаление элемента из BST требует обработки трех принципиально разных случаев :

  1. Узел является листом: вершина просто отвязывается от родителя (удаление 20 оставляет дерево корректным) .
  2. Узел имеет одного потомка: родитель узла перенаправляет свой указатель напрямую на единственного ребенка удаляемой вершины .
  3. Узел имеет двух потомков: удалить его напрямую нельзя, иначе поддеревья потеряют связь . Алгоритм находит ближайшее большее значение — так называемого преемника (in-order successor), который является минимальным элементом в правом поддереве . Значение преемника копируется в удаляемый узел, после чего сам дублирующий лист удаляется из правого поддерева . При удалении узла 30 преемником стал 40 , а при удалении корня 50 новым корнем стал узел 60 .

Балансировка и типовые задачи: от валидации BST до Lowest Common Ancestor 1:03:10

Скорость операций в BST напрямую зависит от его высоты: в сбалансированном дереве высота составляет $\approx \log_2 n$, обеспечивая поиск за $O(\log n)$ . Однако наивное BST уязвимо к порядку входных данных . Если передать значения в отсортированном порядке (от 1 до 7), каждый последующий элемент уходит исключительно вправо, превращая дерево в линейный односвязный список высотой 7 . Тест на 1000 отсортированных числах породил вырожденное дерево высотой 1000, где операции деградировали до худшего случая $O(n)$ . На случайных данных ситуация заметно лучше: для 1000 ключей высота составила 21 (при идеале 10), а для 100 000 ключей — 39 (при идеале 17), что позволило искать ключ за 40 шагов вместо ста тысяч .

Для промышленной защиты от вырождения применяются самобалансирующиеся деревья . При каждой вставке они проверяют баланс весов и выполняют вращения узлов (rotations), удерживая логарифмическую глубину . Классическими решениями здесь выступают АВЛ-деревья и красно-черные деревья, а в файловых системах и реляционных базах данных доминируют B-деревья, сохраняющие множество ключей внутри одной физической страницы . Благодаря балансировке даже 1 000 000 записей укладывается всего в 20 уровней .

На базе деревьев Бодуров разбирает четыре задачи с технических собеседований:

В стандартной библиотеке Python встроенного класса BST нет, а для поддержания отсортированного списка традиционно используется модуль bisect . Тем не менее понимание деревьев критично: на них строятся индексы БД, автодополнение текста (префиксные деревья) и синтаксические деревья (AST) в компиляторах .

🌲 Кучи, очереди с приоритетом и графовые алгоритмы 1:15:30

Бинарная куча: устройство, просеивание и модуль heapq 1:15:30

Бинарная куча (heap) представляет собой полное бинарное дерево, которое исключительно эффективно размещается поверх обычного списка Python . При добавлении нового элемента методом push значение сначала помещается в конец списка — на первое свободное место последнего уровня дерева . Если добавленное число оказывается меньше своего родителя, оно всплывает наверх через серию обменов — эта операция называется sift up (просеивание вверх) . Например, если в кучу [1, 3, 2, 5, 9, 8] добавить 0, ноль попадает по индексу 6, затем меняется местами с родителем 2, следом — с 1 и занимает корень: итоговый массив принимает вид [0, 3, 1, 5, 9, 8, 2] . Поскольку высота полного бинарного дерева составляет около $\log n$, операция добавления выполняется строго за $O(\log n)$ .

Операция извлечения минимума pop забирает элемент из корня . Чтобы не оставлять пустот в структуре данных, на место корня переносится последний элемент списка, после чего запускается процедура sift down (просеивание вниз): элемент сравнивается с обоими потомками и меняется местами с наименьшим из них, пока порядок кучи не восстановится . Так, при извлечении единицы из кучи [1, 3, 2, 5, 9, 8] на вершину временно встаёт 8, которая тут же меняется с двойкой, давая результат [2, 3, 8, 5, 9] за $O(\log n)$ . При этом чтение минимального элемента происходит за $O(1)$ .

В стандартную библиотеку Python входит модуль heapq, реализующий min-кучу . Джавид Бодуров подчёркивает, что куча в Python — это самый обычный список, с которым работают функции heappush и heappop . Последовательное добавление чисел 5, 3, 8, 1, 9, 2 формирует массив [1, 3, 2, 5, 9, 8], а поочерёдное извлечение возвращает элементы в отсортированном порядке: 1, 2, 3, 5, 8, 9 — на этом принципе строится пирамидальная сортировка (Heapsort) за $O(n \log n)$ . Если исходный массив уже существует, функция heapify преобразует его на месте всего за $O(n)$, а не за $O(n \log n)$ :

Так как в Python доступна только min-куча, для эмуляции max-кучи Джавид Бодуров рекомендует инвертировать знаки чисел: минимальное из отрицательных значений соответствует максимальному исходному . Для очередей с приоритетом в кучу передаются кортежи вида (приоритет, данные) . В эксперименте с тремя задачами — отчёт (приоритет 2), баг (приоритет 1) и релиз (приоритет 3) — первым закономерно извлёкся баг .

Кучи также лежат в основе алгоритма поиска $K$ наибольших элементов в потоке данных: вместо полной сортировки создаётся min-куча фиксированного размера $K$ . При поступлении каждого нового числа оно отправляется в кучу, и, если её размер превышает $K$, минимальный элемент сразу выталкивается . В результате в корне кучи всегда остаётся $K$-й по величине элемент . Для списка [3, 2, 1, 5, 6, 4] при $K=2$ алгоритм возвращает 5, а для списка [7, 2, 9, 4, 1, 8, 3] при $K=3$ — число 7 . Подобный подход работает за $O(n \log K)$ по времени и $O(K)$ по памяти . Встроенная функция heapq.nlargest находит 3 наибольших числа среди миллиона за 0,03 секунды, тогда как полная сортировка требует почти 0,5 секунды — разница составляет 17 раз .

Графы: матрица против списка смежности, обходы BFS и DFS 1:23:40

Граф — наиболее гибкая структура данных в программировании; по словам преподавателя, дерево является лишь частным случаем графа без циклов и с одной компонентой связности , . Граф состоит из вершин (vertices) и соединяющих их рёбер (edges), которые могут быть направленными, ненаправленными или взвешенными . Хранить связи можно двумя базовыми методами :

Для обхода всех вершин графа применяются поиск в ширину (BFS) и поиск в глубину (DFS) . BFS использует очередь и множество посещённых узлов, обходя граф концентрическими кругами . В тестовом графе Джавида Бодурова (компонента из вершин $A, B, C, D, E$ и изолированная пара $F-G$) обход BFS из вершины $A$ дал порядок A, B, C, D, E . Напротив, DFS уходит по ветке до тупика и только потом возвращается назад . Рекурсивный DFS из той же вершины $A$ выдал иной порядок: A, B, D, C, E . Итеративная версия DFS с явным пользовательским стеком повторила тот же путь A, B, D, C, E .

Оба поиска требуют времени $O(V + E)$ . BFS идеален для вычисления кратчайшего пути по числу рёбер: расстояние от $A$ до $E$ составило 3 ребра, а путь до $F$ не был найден . DFS незаменим для анализа связности и проверки циклов: отслеживая предка каждой вершины, алгоритм распознаёт цикл, если натыкается на уже посещённую вершину, не являющуюся родителем текущей . В тестовом графе цикл $A-B-D-C-A$ вернул True, тогда как на простой цепочке из трёх вершин проверка выдала False .

Принцип связных компонент в графах позволяет элегантно решать популярные алгоритмические задачи на матрицах (сетках) . Если представить карту земли и воды в виде сетки, ячейки суши становятся вершинами, а их соседи сверху, снизу, справа и слева — рёбрами . Запустив DFS для каждой непосещённой клетки суши, Джавид Бодуров подсчитал количество островов: на тестовой карте размером в 4 строки нашлось 3 острова размерами 4, 1 и 2 клетки с общей сложностью обхода $O(N)$ .

Топологическая сортировка и алгоритм Дейкстры 1:31:25

В направленных ациклических графах (DAG) возникает задача выстраивания зависимостей — топологическая сортировка . В университетском учебном плане курс математики предваряет физику и computer science, а computer science предшествует алгоритмам . Алгоритм подсчитывает число входящих рёбер (in-degree) для каждого узла :

  1. Все вершины с нулевой полустепенью захода помещаются в очередь .
  2. Вершина извлекается из очереди, уменьшая счётчики входящих связей у своих непосредственных соседей .
  3. Как только счётчик соседа падает до нуля, он отправляется в очередь .
  4. В тестовом графе курсов получен строгий порядок: математика $\rightarrow$ физика $\rightarrow$ computer science $\rightarrow$ алгоритмы .

Если в графе присутствует цикл, алгоритм заблокируется, и часть вершин вообще не попадёт в очередь . Свойства полустепеней захода и исхода (in-degree / out-degree) критически важны в веб-индексации: например, поисковые системы рассматривают высокую входящую степень страницы как признак её авторитетности .

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

Джавид Бодуров наглядно иллюстрирует работу алгоритма на графе из 4 вершин ($A, B, C, D$) :

Итоговый вектор кратчайших расстояний от точки $A$ составил A: 0, C: 1, B: 3, D: 4 . Важнейшее ограничение Дейкстры — рёбра не должны содержать отрицательных весов . Итоговая временная сложность составляет $O((V + E) \log V)$, так как каждая операция с очередью приоритетов требует логарифмического времени — именно этот алгоритм обеспечивает работу современных систем автомобильной навигации . В завершение темы графов лектор анонсирует разбор фундаментального механизма, на котором строится DFS — рекурсии .

🔍 Рекурсивные алгоритмы, мемоизация и искусство быстрого поиска 1:40:33

Базовый случай, глубина стека и мемоизация: от факториала до чисел Фибоначчи 1:40:33

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

Для вычисления 10-го числа Фибоначчи функция вызывается 177 раз , а для 30-го числа (равного 832 040) требуется уже более 2 миллионов вызовов . Причина в том, что дерево вычислений многократно дублирует одни и те же подзадачи: значение для аргумента 28 рассчитывается дважды уже на верхних уровнях . Решением становится мемоизация — сохранение промежуточных результатов в словаре . С добавлением словаря количество вызовов для 30-го числа Фибоначчи сокращается с 2 миллионов до всего лишь 59 .

В стандартной библиотеке Python для этого предусмотрен готовый декоратор @lru_cache из модуля functools . С его помощью 100-е число Фибоначчи, состоящее из 21 знака, вычисляется мгновенно, превращая временную сложность из экспоненциальной в $O(n)$ . Этот подход к кэшированию подзадач служит первым шагом к динамическому программированию .

При работе с глубокой рекурсией критически важно помнить об ограничениях среды исполнения. Память стека конечна, и по умолчанию Python ограничивает глубину 1000 фреймами, защищая систему от переполнения . Если вычисление факториала для 900 отрабатывает без проблем, то вызов для 1000 вызывает RecursionError . Предел можно поднять функцией sys.setrecursionlimit, однако Джавид Бодуров предупреждает, что чрезмерное увеличение лимита способно привести к аварийному завершению всей программы . В таких ситуациях рекурсию необходимо переписывать через итеративный цикл или явный собственный стек .

Ханойские башни, быстрое возведение в степень и техника бэктрекинга 1:45:42

Рекурсивный подход незаменим в задачах, где итеративный код выглядит громоздким — в частности, при работе с древовидными структурами и перебором вариантов . Классической иллюстрацией служат Ханойские башни: чтобы перенести пирамиду из $n$ дисков с первого стержня на третий, сначала рекурсивно перемещают $n-1$ дисков на вспомогательный стержень, затем переносят самый большой диск на целевой, после чего возвращают $n-1$ дисков поверх него . Базовым случаем выступает перемещение нуля дисков . Количество шагов здесь строго описывается формулой $2^n - 1$: для 3 дисков требуется 7 перемещений, для 10 — 1023, а для 20 дисков число операций превышает 1 миллион (ровно 1 048 575) . Поскольку каждый новый диск удваивает объем работы, задача для 50 дисков непосильна ни для одного современного компьютера .

Рекурсия также обеспечивает логарифмическое ускорение при делении задачи пополам . Так, наивное вычисление $2^{100}$ требует сотни последовательных умножений, тогда как алгоритм быстрого возведения в степень рассчитывает $2^{n/2} \times 2^{n/2}$ (домножая на основание при нечетном $n$) всего за $O(\log n)$ вызовов с базовым случаем $2^0 = 1$ . Аналогично рекурсия элегантно выравнивает вложенные списки неизвестной глубины: если элемент является числом, он сохраняется, а если списком — функция вызывает сама себя .

Для комбинаторных задач применяется техника поиска с возвратом (backtracking): пошаговое построение решения с откатом назад при попадании в тупик .

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

Линейный и бинарный поиск, модуль bisect и поиск по ответу 1:51:16

Линейный последовательный перебор элементов за $O(n)$ универсален и работает на неотсортированных данных, требуя до миллиона проверок на списке соответствующего размера . Однако на отсортированных коллекциях кардинальное преимущество демонстрирует бинарный поиск с алгоритмической сложностью $O(\log n)$ . Работая по принципу отсечения половины диапазона через указатели левой и правой границы, он находит элемент среди 1 миллиона чисел максимум за 20 итераций, а среди 1 миллиарда — всего за 30 шагов [1:52:48–1:55:00].

Джавид Бодуров обращает внимание на критические ошибки реализации: бинарный поиск на неотсортированном массиве молча возвращает неверный результат (например, выдает -1 для существующего числа 3 в массиве [5, 1, 9, 3, 7]) , а неверные границы (left <= right, смещения mid + 1 и mid - 1) приводят к пропуску значений или бесконечному циклу .

В стандартной библиотеке Python алгоритм инкапсулирован в модуле bisect:

Модуль bisect также позволяет лаконично заменить громоздкие каскады if/elif — например, сопоставляя числовые баллы буквенным оценкам через список пороговых значений .

Кульминацией применения алгоритма выступает методика «бинарного поиска по ответу», где поиск ведется не по готовому массиву, а по пространству возможных решений монотонной функции . Если условие задачи меняет истинность с «нет» на «да» в единственной точке (например, при поиске наименьшего числа, чей квадрат не меньше 2000, где ответом становится 45), бинарный поиск безошибочно вычисляет оптимальное значение, минимальную скорость или предельный размер за логарифмическое время [1:58:40–1:59:37].

🚀 Сортировки, алгоритмические паттерны и стратегия технического собеседования 2:05:45

От квадратичных сортировок к Timsort: как и чем упорядочивать данные 2:05:45

В реальной разработке программистам почти никогда не приходится писать собственные алгоритмы сортировки с нуля . Джавид Бодуров подчеркивает, что в Python базовым инструментом выступают встроенная функция sorted() и списковый метод .sort() . Разница между ними принципиальна: sorted() возвращает совершенно новый список, тогда как метод .sort() мутирует исходную структуру на месте и возвращает None . Классическая ошибка новичков — конструкция вида numbers = numbers.sort(), в результате которой переменная безвозвратно перезаписывается значением None .

Оба механизма поддерживают флаг reverse=True для упорядочивания по убыванию и параметр key . Ключевая функция вызывается ровно один раз для каждого элемента . Например, передав key=len списку строк, можно мгновенно выстроить слова по длине . При этом слова одинаковой длины сохранят исходный взаимный порядок: «груша» (pear) останется перед «киви» (kiwi) . Это свойство называется стабильностью сортировки, и встроенный в Python алгоритм Timsort гарантированно стабилен . Если требуется сложная логика — например, отсортировать студентов по убыванию баллов, а при равенстве баллов по алфавиту имен — достаточно вернуть кортеж: key=lambda x: (-x.score, x.name) .

С точки зрения теории, ни один алгоритм на основе попарных сравнений математически не способен преодолеть барьер $O(n \log n)$ в худшем случае . Обойти это ограничение можно только при наличии дополнительных знаний о структуре данных . Классический пример — сортировка подсчетом (Counting Sort): зная, что возраст людей лежит в диапазоне от 0 до 100, достаточно создать массив из 101 счетчика . Подобный подход отрабатывает за линейное время $O(n + k)$ без единого сравнения .

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

Предварительная сортировка — мощный инженерный прием . Потратив $O(n \log n)$ на упорядочивание массива, разработчик получает возможность объединять списки за один проход, мгновенно выявлять дубликаты и запускать бинарный поиск .

Шесть универсальных паттернов для решения алгоритмических задач 2:10:17

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

  1. Два указателя (Two Pointers) . Применяется на отсортированных данных либо при сравнении элементов с обоих концов . Например, для поиска пары чисел с суммой 10 в массиве [1, 3, 4, 6, 8, 11] левый и правый указатели смещаются навстречу друг другу . Решение находится за 5 шагов , снижая сложность с полного перебора $O(n^2)$ до $O(n)$ по времени и $O(1)$ по памяти .

  2. Скользящее окно (Sliding Window) . Идеально подходит для поиска непрерывных подмассивов и подстрок . При расчете максимальной суммы окна из 3 элементов не нужно складывать тройку заново: достаточно прибавить входящий справа элемент и вычесть выбывающий слева . На окне в 1000 элементов такой подход ускоряет вычисления примерно в 60 раз, трансформируя сложность из $O(n \cdot k)$ в $O(n)$ . Паттерн работает и с плавающим окном: задача о самой длинной подстроке без повторяющихся символов решается за один проход с помощью хеш-таблицы последних индексов символов .

  3. Префиксные суммы (Prefix Sum) . Незаменимы при многократных запросах суммы элементов на отрезке . Предварительно сформировав массив накопленных сумм за $O(n)$, сумму любого диапазона можно получить ровно за одну операцию вычитания $O(1)$ . Комбинация префиксных сумм со словарем позволяет за линейное время находить количество подмассивов с заданной суммой .

  4. Быстрый и медленный указатели (Fast and Slow Pointers) . Применяется в связных списках для поиска циклов и нахождения середины за один проход . Быстрый указатель шагает на два узла, медленный — на один; при наличии цикла быстрый неизбежно догонит медленного, требуя лишь $O(1)$ дополнительной памяти .

  5. Слияние интервалов (Merging Intervals) . Используется в задачах на перекрытие временных слотов или встреч . Интервалы сортируются по времени начала, после чего последовательно сливаются, если начало следующего отрезка лежит внутри текущего . Итоговая сложность упирается в сортировку — $O(n \log n)$ .

  6. Динамическое программирование (Dynamic Programming) . Применяется при наличии повторяющихся подзадач для сохранения ранее вычисленных промежуточных состояний . Классическая задача о подъеме по лестнице на 1 или 2 ступени без сохранения промежуточных значений привела бы к зависанию рекурсии: для 40 ступеней число комбинаций превышает 165 миллионов . А поиск максимального подмассива (алгоритм Кадане) решается за $O(n)$ времени и $O(1)$ памяти простым выбором: расширить текущую сумму или начать цепочку заново с текущего элемента .

Семь шагов лайвкодинга: стратегия прохождения интервью и разбор типовых задач 2:18:59

Техническое собеседование — это не просто проверка знаний, а оценка того, как кандидат мыслит и аргументирует свои решения под давлением . Бодуров предлагает строгий регламент из семи шагов :

Эту схему автор демонстрирует на четырех классических задачах с собеседований:

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

💬 Цитаты

«It doesn't give us seconds. It give us the shape of the grows.»

Джавид Бодуров 03:20

«The real superpower is not the insert itself but the fact that nothing moves.»

Джавид Бодуров 25:03

«When you need a queue in Python do don't use a list, use a deque.»

Джавид Бодуров 37:26

«When you need only the best few, do not sort everything.»

Джавид Бодуров 1:23:00

«A tree is a special graph and the graph is a tree without the rules.»

Джавид Бодуров 1:23:54

«If the list is not sorted, the binary search gives wrong answer and it does it quietly.»

Джавид Бодуров 1:55:27

«A coding interview is not only a test of what you know. It is a test of how you think and how you talk about the problem.»

Джавид Бодуров 2:19:11
👥 Спикер
📖 Термины
Нотация Big O
Способ оценки асимптотической сложности алгоритма, показывающий характер роста числа операций или памяти относительно объема входных данных.
Хеш-таблица
Структура данных для хранения пар «ключ — значение», обеспечивающая поиск и вставку в среднем за константное время O(1).
Бинарное дерево поиска (BST)
Древовидная структура данных, где значения в левом поддереве каждого узла меньше родительского, а в правом — больше.
Бинарная куча (Heap)
Специализированное дерево, позволяющее извлекать минимальный или максимальный элемент за O(log n) и строить структуру из массива за O(n).
Мемоизация
Кэширование результатов выполнения рекурсивных функций для предотвращения повторных вычислений на одних и тех же входных данных.
Timsort
Встроенный в Python гибридный стабильный алгоритм сортировки, объединяющий сортировку слиянием и сортировку вставками.
Технологии и IT Джавид Бодуров Python Big O Алгоритмы и структуры данных Timsort