Чтобы добавить миллион элементов в список Python, памяти приходится перераспределяться всего 87 раз, а бинарный поиск через модуль bisect ускоряет работу программы в 28 000 раз по сравнению с обычным перебором. Джавид Бодуров разбирает механику фундаментальных структур данных и алгоритмов «под капотом» Python — от устройства динамических массивов и хеш-таблиц до графов, мемоизации и гибридной сортировки Timsort. Этот гид систематизирует ключевые паттерны решения задач и показывает, как превратить сухой анализ сложности Big O в главный инструмент на технических интервью.
🧱 Основы алгоритмической сложности и базовые структуры данных 0:00
Анализ сложности алгоритмов и нотация Big O 2:55
Преподаватель курса Джавид Бодуров (Javid Bodurov) подчеркивает, что сравнение скорости работы программ по физическому времени в секундах бессмысленно: один и тот же скрипт может быстро выполниться на ноутбуке и зависнуть на телефоне . Единственный объективный критерий эффективности — зависимость количества базовых шагов от размера входных данных, которую описывает нотация Big O .
Джавид выделяет шесть основных категорий временной сложности, деля их на «хорошие» и «опасные»:
- $O(1)$ (константная сложность) — число операций не зависит от объема данных . Обращение по индексу к списку из 10 элементов или 1 миллиона всегда занимает один шаг .
- $O(\log n)$ (логарифмическая) — при каждом шаге объем задачи делится пополам (принцип бинарного поиска) . Для 10 элементов худший случай требует 4 шагов, для 1000 — 10, а для 1 миллиона — всего 20 операций .
- $O(n)$ (линейная) — объем работы растет строго пропорционально входу . Последовательный перебор 1 миллиона элементов потребует ровно 1 миллион проверок .
- $O(n \log n)$ (линейно-логарифмическая) — типичная сложность эффективных алгоритмов сортировки, где для 1000 элементов требуется порядка 10 000 операций .
- $O(n^2)$ (квадратичная) — возникает при вложенных циклах . Если для 10 элементов выполняется 100 шагов, то для 1000 элементов счетчик возрастает до 1 миллиона .
- $O(2^n)$ (экспоненциальная) — худший сценарий, где каждый новый элемент удваивает объем работы . Вычисление 30-го числа Фибоначчи через наивную рекурсию вызывает 2 692 537 вызовов функций , а перебор всех подмножеств для 30 элементов превышает 1 миллиард комбинаций .
Для наглядности Бодуров сопоставляет все шесть типов на массиве из 1000 элементов: если константный алгоритм сделает 1 шаг, то квадратичный выполнит 1 000 000, а экспоненциальный выдаст число с более чем 300 знаками .
Для быстрой практической оценки кода применяются три базовых правила:
- Отбрасывание констант: алгоритм, делающий $2n$ операций или содержащий три последовательных цикла по $n$, все равно признается $O(n)$, так как форма графика остается линейной .
- Учет только старшего слагаемого: в выражении $n^2 + n$ младшая часть для 1000 элементов составляет всего 1000 против 1 миллиона, поэтому итоговая сложность записывается как $O(n^2)$ .
- Ориентация на худший случай: гарантия выполнения строится на сценарии, когда искомый элемент находится в самом конце или отсутствует вовсе .
Устройство памяти и работа массивов в 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)$ .
Цена операций кардинально зависит от точки вмешательства:
- Вставка (
insert(0, val)) или удаление (pop(0)) в начале списка требуют физического сдвига всех существующих элементов вправо или влево, что дает $O(n)$ , . - Поиск элемента через оператор
inили метод.index()выполняет последовательный опрос всех ячеек, требуя времени $O(n)$ . - Срезы (
list[2:5]) создают физическую копию элементов , тогда как простое присвоение (y = x) лишь создает второе имя для исходного объекта . -
Создание матрицы умножением списка `[[0]
-
3]
- 3
дублирует одну и ту же ссылку, из-за чего изменение ячейки в одной строке меняет значения во всей сетке; правильный путь — списковое включение[[0]*3 for _ in range(3)]` , .
Односвязные и двусвязные списки 19:20
Главным ограничением динамических массивов остается дороговизна вставки в середину и начало . Связный список решает эту проблему за счет отказа от непрерывного хранения данных: каждый элемент (узел/node) может располагаться в любом свободном секторе памяти . Узел состоит всего из двух полей: полезной нагрузки (value) и указателя на следующий элемент (next) .
Входом в такую цепочку служит указатель head (голова) . Платой за фрагментированное размещение становится потеря быстрого доступа по индексу: чтобы прочитать значение на позиции 500 000, программе приходится выполнить ровно 500 000 переходов по ссылкам, что снижает скорость произвольного доступа до $O(n)$ , .
Суперсила связного списка раскрывается при мутациях структуры :
- Вставка в середину: чтобы вставить узел со значением
15между узлами10и20, достаточно перенаправить ссылку нового узла на20, а затем ссылку узла10— на новый элемент . Никакие данные в памяти не сдвигаются . Критически важен порядок: сначала связывается «будущее», и только потом переписывается «прошлое», иначе потеряется остаток цепочки . - Вставка в голову: указатель нового узла направляется на текущий
head, после чего самheadпереназначается на новый узел — операция занимает строго $O(1)$ независимо от того, содержит ли список 3 или 1 000 000 узлов , . - Удаление: исключение узла требует лишь переброски указателя его предшественника в обход удаляемого элемента (
prev.next = target.next), после чего сборщик мусора Python автоматически очищает память , .
Единственный подвох кроется в поиске точки изменения: чтобы удалить или вставить элемент, до него нужно дойти от головы за $O(n)$ . Для эффективной работы с концом списка вводится дополнительный указатель tail (хвост), снижающий сложность вставки в конец до $O(1)$ . Тем не менее односвязный список позволяет двигаться только в одном направлении, что создает предпосылки для внедрения двусвязных структур .
🥞 Стеки, очереди и хеш-таблицы: базовые кирпичики быстрых программ 27:16
Ранее в разговоре Джавид Бодуров касался связных списков и массивов, сравнивая их поведение по памяти и скорости доступа. Опираясь на эти фундаментальные концепции, программисты строят специализированные структуры данных, оптимизированные под конкретные сценарии взаимодействия с элементами.
Стеки, принцип LIFO и механизм стека вызовов 27:16
Стек — это коллекция, в которой добавление и извлечение элементов происходят строго на одном конце, называемом верхушкой (top) . В реальной жизни аналогом служит стопка тарелок на кухне: чистую тарелку кладут наверх стопки, и при необходимости берут тоже самую верхнюю . Попытка вытащить тарелку снизу приведет к падению всей конструкции . Этот принцип упорядочивания называется LIFO — Last In, First Out («последним пришел — первым вышел») .
У стека выделяют три базовые операции :
push— добавление нового элемента на верхушку стека ;pop— удаление элемента с верхушки и его возврат ;peek— просмотр верхнего элемента без его фактического удаления из структуры .
В Python для создания стека не требуется писать отдельный класс: стандартный список (list) уже идеально выполняет эту роль . Метод append() выступает в роли операции push , чтение по индексу [-1] реализует peek , а встроенный метод pop() извлекает последний добавленный элемент . Если попытаться вызвать pop() на пустом списке, интерпретатор выбросит ошибку IndexError . Поскольку операции затрагивают только конец списка и элементы не сдвигаются в памяти, операции push, pop и peek выполняются за константное время $O(1)$ .
На практике со стеками разработчик сталкивается постоянно:
- Кнопка отмены действий (Undo): каждое изменение в текстовом редакторе отправляется на вершину стека, а при нажатии Ctrl+Z последняя правка снимается со стека и аннулируется .
- Кнопка «Назад» в веб-браузере: посещенные страницы сохраняются в стеке, и при возврате текущая вкладка снимается, открывая предыдущую .
- Стек вызовов функций (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)$, что в тысячи раз быстрее обычного списка .
Очереди незаменимы в задачах распределения ресурсов:
- спулинг печати: документы отправляются на принтер и распечатываются строго в порядке поступления ;
- обработка клиентских обращений в службах технической поддержки ;
- асинхронные очереди сообщений в бэкенд-архитектурах, где задачи (например, отправка email) изолируются от основного потока вычислений, гарантируя отказоустойчивость .
На базе очереди реализуется фундаментальный алгоритм обхода — поиск в ширину (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 :
- Слово «Apple» дает сумму кодов 530; $530 \pmod 8 = 2$ — значение отправляется во 2-ю ячейку ;
- Слово «Banana» дает сумму 609; $609 \pmod 8 = 1$ — в 1-ю ячейку ;
- Слово «Cherry» дает 653; $653 \pmod 8 = 5$ — в 5-ю ячейку ;
- Слово «Grape» дает 527; $527 \pmod 8 = 7$ — в 7-ю ячейку .
Неизбежная проблема хеш-таблиц — коллизии, когда два совершенно разных ключа претендуют на один и тот же индекс . Например, анаграммы «melon» и «lemon» имеют идентичную сумму кодов букв (539) и обе претендуют на 3-ю ячейку . Для разрешения подобных конфликтов используются две стратегии:
- Метод цепочек (Chaining): каждая ячейка таблицы содержит не одиночный элемент, а связный список пар «ключ-значение» . При возникновении коллизии элемент просто дописывается в конец списка соответствующей ячейки .
- Открытая адресация (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) . Для этого существует четыре классических алгоритма, три из которых опираются на рекурсию :
- Прямой обход (Pre-order): сначала обрабатывается текущий узел, затем левое поддерево, после чего правое . На тестовом дереве порядок дает последовательность 1, 2, 4, 5, 3 .
- Центрированный обход (In-order): левое поддерево, текущий узел, правое поддерево . Результат работы алгоритма — 4, 2, 5, 1, 3 .
- Обратный обход (Post-order): левое поддерево, правое поддерево, затем сам узел . Последовательность принимает вид 4, 5, 2, 3, 1 . Этот способ незаменим, когда дочерние элементы нужно обработать раньше родительских — например, при каскадном удалении папки со всем ее содержимым .
- Обход по уровням (Level-order): дерево сканируется горизонтально, уровень за уровнем сверху вниз, порождая порядок 1, 2, 3, 4, 5 . В отличие от первых трех, здесь задействуется очередь (FIFO): корень кладется в очередь, после чего в цикле извлекается первый элемент, обрабатывается, а его потомки добавляются в хвост . По сути, это реализация поиска в ширину (BFS) .
Каждый из четырех способов гарантированно посещает каждый узел ровно один раз, что дает временную сложность $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 требует обработки трех принципиально разных случаев :
- Узел является листом: вершина просто отвязывается от родителя (удаление 20 оставляет дерево корректным) .
- Узел имеет одного потомка: родитель узла перенаправляет свой указатель напрямую на единственного ребенка удаляемой вершины .
- Узел имеет двух потомков: удалить его напрямую нельзя, иначе поддеревья потеряют связь . Алгоритм находит ближайшее большее значение — так называемого преемника (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 уровней .
На базе деревьев Бодуров разбирает четыре задачи с технических собеседований:
- Итеративный In-Order без рекурсии: рекурсивный стек вызовов заменяется явным стеком . Алгоритм идет влево до упора, складывая узлы в стек, а затем снимает вершину, выводит ее и делает шаг в правое поддерево . Это спасает от ошибки переполнения стека (stack overflow), лимит которого в Python составляет порядка 1000 вызовов .
- Валидация двоичного дерева поиска: наивная проверка условия «левый ребенок меньше, а правый больше» фатально ошибочна . Если у корня 10 левый потомок равен 5, а у него правый равен 15, локальное сравнение подтвердит корректность, но глобально 15 нарушает инвариант корня . Верное решение пробрасывает вниз допустимый интервал
(min_val, max_val): при шаге влево родителем ограничивается верхняя планка, при шаге вправо — нижняя . Сложность проверки линейна — $O(n)$ . - Инверсия бинарного дерева: зеркальное отражение структуры выполняется взаимной перестановкой левого и правого поддеревьев каждого узла через базовый рекурсивный шаблон .
- Наименьший общий предок (LCA) в BST: для нахождения общего предка двух узлов достаточно одного прохода от корня: если оба искомых значения меньше текущего ключа, спуск идет влево, если оба больше — вправо . Как только пути расходятся, текущий узел и является ответом, что выполняется за $O(\log n)$ . Для пары 20 и 40 общим предком оказался 30, а для 20 и 80 — корень 50 .
В стандартной библиотеке 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)$ :
- Преобразование списка
[9, 4, 7, 1, 8, 2]черезheapifyдаёт[1, 4, 2, 9, 8, 7]; - На тесте с 1 000 000 случайных чисел
heapifyотработал за 0,07 секунды, тогда как миллион вызововheappushпотребовал 1,1 секунды ; - При 1000 извлечений минимального элемента из массива в 1 000 000 чисел
heappopзанял около 4 мс, тогда как вызовpop(0)у отсортированного списка отнял около 370 мс — куча оказалась быстрее в 90 раз .
Так как в 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), которые могут быть направленными, ненаправленными или взвешенными . Хранить связи можно двумя базовыми методами :
- Матрица смежности (Adjacency Matrix) — двумерная таблица $N \times N$, где проверка смежности выполняется за $O(1)$ . Главный минус — квадратичный расход памяти $O(V^2)$: для графа из 7 вершин и 6 рёбер таблица требует 49 ячеек, из которых полезными единицами заполнены лишь 12 (каждое ребро дублируется) . Для сети в 1 000 000 человек матрица потребовала бы триллион ячеек ;
- Список смежности (Adjacency List) — словарь Python, ключами которого выступают вершины, а значениями — списки их соседей . Потребление памяти составляет всего $O(V + E)$ . Для графа из 1000 вершин и 3000 рёбер матрице нужно 1 000 000 ячеек, а списку смежности — всего 6000 записей .
Для обхода всех вершин графа применяются поиск в ширину (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) для каждого узла :
- Все вершины с нулевой полустепенью захода помещаются в очередь .
- Вершина извлекается из очереди, уменьшая счётчики входящих связей у своих непосредственных соседей .
- Как только счётчик соседа падает до нуля, он отправляется в очередь .
- В тестовом графе курсов получен строгий порядок: математика $\rightarrow$ физика $\rightarrow$ computer science $\rightarrow$ алгоритмы .
Если в графе присутствует цикл, алгоритм заблокируется, и часть вершин вообще не попадёт в очередь . Свойства полустепеней захода и исхода (in-degree / out-degree) критически важны в веб-индексации: например, поисковые системы рассматривают высокую входящую степень страницы как признак её авторитетности .
Когда рёбра графа получают вес (стоимость, расстояние или время), обычный поиск в ширину перестаёт находить оптимальный маршрут . Решением становится алгоритм Дейкстры, модифицирующий BFS заменой стандартной очереди на min-кучу . Алгоритм хранит текущие кратчайшие расстояния до всех вершин, начиная со стартовой с весом 0 . На каждом шаге из кучи вынимается узел с наименьшим накопленным расстоянием, после чего проверяется возможность улучшить (релаксировать) дистанцию до его соседей .
Джавид Бодуров наглядно иллюстрирует работу алгоритма на графе из 4 вершин ($A, B, C, D$) :
- Ребро $A \rightarrow B$ имеет вес 4, а путь $A \rightarrow C$ стоит 1 ;
- Ребро $C \rightarrow B$ стоит 2, $B \rightarrow D$ — 1, а прямое ребро $C \rightarrow D$ — 5 ;
- Прямая дорога из $A$ в $B$ обходится в 4, но составной маршрут через $C$ оказывается короче: $1 + 2 = 3$ ;
- До вершины $D$ оптимальный путь проходит по цепочке $A \rightarrow C \rightarrow B \rightarrow D$ с общей стоимостью 4, тогда как прямой переход $C \rightarrow D$ дал бы сумму 6 .
Итоговый вектор кратчайших расстояний от точки $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): пошаговое построение решения с откатом назад при попадании в тупик .
- Генерация всех подмножеств списка: для каждого элемента есть два выбора — включить его или исключить, что для 3 элементов дает 8 подмножеств, а для 4 элементов — 16 вариантов ($2^n$) .
- Поиск перестановок: выбор первого элемента всеми возможными способами с рекурсивным упорядочиванием хвоста, что для $n$ элементов формирует $n!$ комбинаций (6 перестановок для 3 элементов и 24 для четырех) .
Джавид Бодуров выделяет три золотых правила написания рекурсии: всегда начинать код с базового случая , доверять корректности рекурсивного вызова для уменьшенной подзадачи и строго контролировать, чтобы каждый шаг приближал состояние к условию выхода .
Линейный и бинарный поиск, модуль 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_leftопределяет индекс элемента либо позицию для его корректной вставки . - Функция
insortвыполняет вставку с сохранением сортировки массива (поиск точки занимает $O(\log n)$, хотя сам сдвиг элементов в памяти списка стоит $O(n)$) . - На тесте из 1 миллиона чисел встроенный
bisectсработал менее чем за 1 микросекунду, оказавшись в 28 000 раз быстрее линейного перебора .
Модуль 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)$ без единого сравнения .
Для технических интервью Бодуров советует твердо знать классические алгоритмы :
- Пузырьковая сортировка (Bubble Sort) и сортировка выбором (Selection Sort) просты, но работают за неэффективные $O(n^2)$ .
- Сортировка слиянием (Merge Sort) делит массив пополам и гарантирует $O(n \log n)$, однако требует выделения дополнительной памяти под вспомогательные массивы .
- Быстрая сортировка (Quick Sort) в среднем работает за $O(n \log n)$, но при неудачном выборе опорного элемента деградирует до худшего случая $O(n^2)$ .
- Timsort объединяет сортировку слиянием и вставками, демонстрируя $O(n)$ на уже упорядоченных данных и $O(n \log n)$ в худшем .
Предварительная сортировка — мощный инженерный прием . Потратив $O(n \log n)$ на упорядочивание массива, разработчик получает возможность объединять списки за один проход, мгновенно выявлять дубликаты и запускать бинарный поиск .
Шесть универсальных паттернов для решения алгоритмических задач 2:10:17
Большинство задач на алгоритмических секциях не являются уникальными и сводятся к ограниченному набору шаблонов . Джавид Бодуров выделяет шесть ключевых паттернов, распознавание которых позволяет свести решение к шаблонным действиям :
-
Два указателя (Two Pointers) . Применяется на отсортированных данных либо при сравнении элементов с обоих концов . Например, для поиска пары чисел с суммой 10 в массиве
[1, 3, 4, 6, 8, 11]левый и правый указатели смещаются навстречу друг другу . Решение находится за 5 шагов , снижая сложность с полного перебора $O(n^2)$ до $O(n)$ по времени и $O(1)$ по памяти . -
Скользящее окно (Sliding Window) . Идеально подходит для поиска непрерывных подмассивов и подстрок . При расчете максимальной суммы окна из 3 элементов не нужно складывать тройку заново: достаточно прибавить входящий справа элемент и вычесть выбывающий слева . На окне в 1000 элементов такой подход ускоряет вычисления примерно в 60 раз, трансформируя сложность из $O(n \cdot k)$ в $O(n)$ . Паттерн работает и с плавающим окном: задача о самой длинной подстроке без повторяющихся символов решается за один проход с помощью хеш-таблицы последних индексов символов .
-
Префиксные суммы (Prefix Sum) . Незаменимы при многократных запросах суммы элементов на отрезке . Предварительно сформировав массив накопленных сумм за $O(n)$, сумму любого диапазона можно получить ровно за одну операцию вычитания $O(1)$ . Комбинация префиксных сумм со словарем позволяет за линейное время находить количество подмассивов с заданной суммой .
-
Быстрый и медленный указатели (Fast and Slow Pointers) . Применяется в связных списках для поиска циклов и нахождения середины за один проход . Быстрый указатель шагает на два узла, медленный — на один; при наличии цикла быстрый неизбежно догонит медленного, требуя лишь $O(1)$ дополнительной памяти .
-
Слияние интервалов (Merging Intervals) . Используется в задачах на перекрытие временных слотов или встреч . Интервалы сортируются по времени начала, после чего последовательно сливаются, если начало следующего отрезка лежит внутри текущего . Итоговая сложность упирается в сортировку — $O(n \log n)$ .
-
Динамическое программирование (Dynamic Programming) . Применяется при наличии повторяющихся подзадач для сохранения ранее вычисленных промежуточных состояний . Классическая задача о подъеме по лестнице на 1 или 2 ступени без сохранения промежуточных значений привела бы к зависанию рекурсии: для 40 ступеней число комбинаций превышает 165 миллионов . А поиск максимального подмассива (алгоритм Кадане) решается за $O(n)$ времени и $O(1)$ памяти простым выбором: расширить текущую сумму или начать цепочку заново с текущего элемента .
Семь шагов лайвкодинга: стратегия прохождения интервью и разбор типовых задач 2:18:59
Техническое собеседование — это не просто проверка знаний, а оценка того, как кандидат мыслит и аргументирует свои решения под давлением . Бодуров предлагает строгий регламент из семи шагов :
- Шаг 1: Переформулировать задачу своими словами и задать уточняющие вопросы о граничных условиях (пустой массив, дубликаты, предельные размеры) .
- Шаг 2: Записать 1–2 собственных примера данных, включая крайний случай .
- Шаг 3: Озвучить наивное решение «в лоб» (brute force) — даже медленный рабочий вариант подтверждает понимание задачи .
- Шаг 4: Подобрать оптимальный паттерн или структуру данных для улучшения решения .
- Шаг 5: Написать чистый код, проговаривая каждое действие вслух .
- Шаг 6: Построчно протестировать код на ранее подготовленных примерах .
- Шаг 7: Оценить временную и пространственную сложность в нотации Big O .
Эту схему автор демонстрирует на четырех классических задачах с собеседований:
- Валидация скобок (Valid Parentheses) . Решается с помощью ранее изученного стека: открывающая скобка кладется в стек, а при встрече закрывающей верхний элемент извлекается для сверки . Строка сбалансирована, если к финалу стек пуст, что дает $O(n)$ по времени и памяти .
- Лучшее время для покупки акций (Best Time to Buy and Sell Stock) . Вместо перебора всех пар дней за $O(n^2)$ достаточно одного линейного прохода . Отслеживая минимальную встреченную цену и обновляя потенциальную прибыль на каждом шаге, мы получаем оптимальный результат за $O(n)$ времени и $O(1)$ памяти .
- Произведение массива кроме самого элемента (Product of Array Except Self) . В условиях запрета деления задача решается двумя проходами: слева направо формируются префиксные произведения, а вторым проходом справа — постфиксные множители, что укладывается в $O(n)$ времени без дополнительной памяти .
- Поиск пропущенного числа (Missing Number) . В массиве от $0$ до $n$ пропущено ровно одно число. Сортировка займет $O(n \log n)$, использование хеш-множества потребует $O(n)$ памяти, но идеальный ответ дает формула суммы арифметической прогрессии Гаусса: из теоретической суммы вычитается сумма элементов массива, решая задачу за $O(n)$ времени и $O(1)$ памяти .
Главный совет Бодурова для лайвкодинга — думать вслух . Молчание лишает интервьюера возможности помочь кандидату подсказкой . Ошибки естественны, и ключевым фактором успеха становится спокойная реакция и системная регулярная практика решения задач .