Алгоритмы на Python: от основ до продвинутых техник

Введение: Python для алгоритмов и оценка сложности

Зачем Python в алгоритмах

Python часто выбирают для изучения алгоритмов по трём причинам:

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

Богатая стандартная библиотека: многие базовые структуры данных уже реализованы.

Быстрый цикл экспериментов: можно быстро написать, проверить, измерить и улучшить решение.

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

Что такое алгоритм в контексте курса

В рамках курса алгоритм — это:

точный набор шагов для решения задачи;

решение, которое корректно работает на всех допустимых входных данных;

решение, эффективность которого можно оценить.

Мы будем стремиться к решениям, которые:

корректны;

читаемы;

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

Минимальный набор Python-инструментов для алгоритмов

Ввод и вывод

В учебных и соревновательных задачах часто важна скорость ввода.

Для обычных задач достаточно input().

Для больших входных данных полезно читать из sys.stdin.buffer.

Пример быстрого чтения целых чисел:

Вывод обычно делают через print(), но при большом количестве строк может быть выгодно собирать строки в список и печатать один раз:

Стандартные структуры данных

Python даёт готовые структуры, которые мы будем активно использовать:

list — динамический массив.

tuple — неизеняемая последовательность.

dict — хеш-таблица (ассоциативный массив).

set — множество на основе хеш-таблицы.

collections.deque — двусторонняя очередь.

heapq — очередь с приоритетом (минимальная куча).

Документация:

Модуль collections

Модуль heapq

Почему нужно уметь оценивать сложность

Оценка сложности отвечает на вопрос: как изменится время работы и расход памяти, если размер входных данных вырастет?

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

Главная идея:

мы оцениваем рост затрат при увеличении ;

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

Нотация (Big O)

Интуитивное определение

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

Здесь:

— размер входа (например, длина массива, число вершин графа, количество строк);

— форма роста (например, , , ).

Важно: Big O — это про порядок роста, а не про точное время в секундах.

Типичные классы сложности

| Обозначение | Название | Пример ситуации | |---|---|---| | | константная | доступ к a[i] у списка | | | логарифмическая | бинарный поиск | | | линейная | один проход по массиву | | | линейно-логарифмическая | сортировка сравнениями | | | квадратичная | двойной цикл по всем парам | | | экспоненциальная | полный перебор подмножеств |

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

Как оценивать сложность на практике

Правило: считаем доминирующие операции

Мы обычно оцениваем количество повторений “основной” операции:

сравнение;

присваивание;

обращение к элементу;

вставка/удаление.

Если основная операция повторяется примерно раз, это ; если раз — .

Циклы

1) Один цикл по массиву длины :

Сложность по времени: , потому что цикл выполняется раз.

2) Вложенные циклы (все пары):

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

Логарифм и бинарный поиск

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

Интуиция:

было вариантов;

после 1 шага стало примерно ;

после 2 шагов — ;

после шагов — примерно .

Мы останавливаемся, когда остаётся 1 вариант. Это означает , отсюда , поэтому .

Здесь:

— число шагов;

— исходный размер поиска;

— логарифм по основанию 2 (в алгоритмах основание обычно не важно для Big O).

Рекурсия: что важно отслеживать

У рекурсивных алгоритмов обычно оценивают:

глубину рекурсии (сколько уровней вызовов);

сколько работы делается на каждом уровне.

Простой пример:

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

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

Время и память: две разные сложности

Временная сложность

Это количество вычислений. Именно оно чаще всего определяет, пройдёт ли решение ограничение по времени.

Пространственная сложность

Это объём дополнительной памяти, не считая входных данных.

Примеры:

Если вы создаёте массив длины , дополнительная память обычно .

Если алгоритм использует только несколько переменных, это .

Баланс часто выглядит так:

иногда можно ускориться, используя больше памяти;

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

Средний случай, худший случай и амортизированная сложность

Средний и худший случаи

Некоторые операции быстры обычно, но могут быть медленнее на специально подобранных данных.

Например, dict и set в Python имеют:

среднюю сложность операций поиска/вставки около ;

но теоретически возможны редкие ухудшения.

Для алгоритмического мышления важно различать:

худший случай (гарантия при любых входах);

средний случай (типичное поведение).

Амортизированная сложность

Амортизированная сложность — это когда редкие дорогие операции “размазываются” по множеству дешёвых.

Классический пример — list.append(x):

обычно добавление в конец быстрое;

иногда список расширяет внутренний буфер, и это стоит дороже;

но в среднем на длинной серии добавлений получается около на операцию.

Как измерять производительность в Python

Оценка Big O говорит о росте, но не даёт точного времени. Для практики полезно уметь измерять.

timeit

Для микробенчмарков используйте модуль timeit:

Модуль timeit

Пример идеи (не “истина в последней инстанции”, но хороший инструмент):

Правила измерений:

прогревайте код несколькими запусками;

измеряйте несколько раз;

сравнивайте альтернативы на одинаковых данных.

Частые ошибки новичков в оценке сложности

1) Путать “быстро на моём тесте” и “быстро по асимптотике”.

2) Не замечать вложенность:

два последовательных цикла по — это ;

два вложенных цикла по — это .

3) Считать, что сортировка — это “почти линейно”. На практике сортировка сравнением обычно .

4) Игнорировать память: решение может быть быстрым, но не проходить по лимиту памяти.

Как эта статья связана с остальным курсом

Дальше мы будем строить курс так:

сначала закрепим базовые приёмы работы с массивами, строками, хеш-таблицами и очередями;

затем перейдём к классическим алгоритмам: поиск, сортировки, два указателя, префиксные суммы;

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

Почти в каждой теме мы будем делать одно и то же:

формулировать идею;

писать реализацию на Python;

оценивать время и память через Big O;

обсуждать Python-нюансы, влияющие на константы.

Краткое резюме

Python удобен для изучения алгоритмов, но требует внимания к эффективности.

Big O описывает порядок роста времени/памяти при увеличении размера входа .

Один цикл по данным — часто , вложенные циклы по всем парам — .

Бинарный поиск — типичный пример .

В Python важно учитывать особенности стандартных структур данных и уметь измерять код с timeit.

Базовые структуры данных в Python

Связь с предыдущей темой

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

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

Что такое структура данных и почему она важна

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

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

поиск в list обычно линейный

поиск в set и dict обычно константный

извлечение минимального из heapq логарифмическое

Ключевой принцип Python: изменяемость и хешируемость

Перед тем как разбирать конкретные контейнеры, важно понять две базовые идеи.

Изменяемость

list, dict, set, deque — изменяемые (можно менять содержимое).

tuple, str — неизменяемые (после создания “содержимое” не меняется).

Это влияет и на стиль кода, и на возможность использовать объект как ключ.

Хешируемость

Объект хешируем, если его можно безопасно использовать как ключ в dict или как элемент set.

обычно хешируемы: int, float, str, tuple (если внутри тоже хешируемые)

обычно не хешируемы: list, dict, set

Причина практическая: если объект меняется, его хеш мог бы “сломаться”, и структура данных потеряла бы элемент.

list: динамический массив

list — базовый контейнер для последовательностей.

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

нужно хранить элементы в порядке

нужен быстрый доступ по индексу

часто добавляем в конец

Типовые операции и сложность

| Операция | Пример | Типичная сложность | Комментарий | |---|---|---|---| | Доступ по индексу | a[i] | | Быстрый случай | | Изменение по индексу | a[i] = x | | | | Добавление в конец | a.append(x) | амортизированно | Иногда происходит расширение буфера | | Удаление с конца | a.pop() | | | | Вставка в середину/начало | a.insert(0, x) | | Нужно сдвигать элементы | | Удаление из середины/начала | a.pop(0) | | Сдвиги | | Проверка наличия | x in a | | Линейный поиск |

Частые алгоритмические паттерны

проход одним циклом: подсчёты, максимум/минимум, фильтрация

сортировка: a.sort() или sorted(a)

Ссылки:

Тип list

sorted

Подводные камни

a = b не копирует список, а создаёт вторую ссылку

копия: a_copy = a[:] или a_copy = a.copy()

двумерные списки нельзя создавать так: [[0]m]n (строки будут ссылаться на один и тот же список)

Пример правильного создания матрицы:

tuple: неизменяемая последовательность

tuple похож на list, но неизменяем.

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

нужно гарантировать, что набор значений не изменится

нужно использовать последовательность как ключ в dict или элемент set

удобно хранить пары и тройки: координаты, интервалы, ребра

Пример:

Ссылка:

Тип tuple

dict: отображение ключ → значение (хеш-таблица)

dict — одна из самых сильных сторон Python для алгоритмов.

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

нужно быстро находить значение по ключу

нужно считать частоты

нужно хранить “последнее встреченное” или “лучшее найденное” для состояния

Типовые операции и сложность

В среднем (типичный случай):

| Операция | Пример | Типичная сложность | |---|---|---| | Вставка/обновление | d[k] = v | | | Получение | d[k] | | | Проверка наличия ключа | k in d | | | Удаление | del d[k] | |

Полезные приёмы

безопасное получение: d.get(k, default)

подсчёт частот: collections.Counter

“словарь списков” через setdefault или defaultdict

Пример подсчёта частот:

Пример defaultdict(list) для группировки:

Ссылки:

Тип dict

collections.Counter

collections.defaultdict

set: множество (хеш-таблица)

set хранит уникальные элементы и оптимален для проверок принадлежности.

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

нужно быстро проверять “видели ли мы элемент”

нужно удалить дубликаты

нужны операции теории множеств: пересечение, объединение

Типовые операции и сложность

| Операция | Пример | Типичная сложность | |---|---|---| | Добавить | s.add(x) | | | Проверить наличие | x in s | | | Удалить | s.remove(x) / s.discard(x) | |

Важно различать:

remove(x) бросает ошибку, если элемента нет

discard(x) не бросает ошибку

Ссылки:

Тип set

collections.deque: двусторонняя очередь

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

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

BFS (поиск в ширину) в графах

“скользящее окно”, когда добавляем справа и удаляем слева

любая очередь задач

Почему не list

list.pop(0) — из-за сдвига

deque.popleft() —

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

Ссылка:

collections.deque

heapq: очередь с приоритетом (минимальная куча)

Модуль heapq реализует минимальную кучу поверх обычного списка.

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

нужно много раз извлекать минимум

алгоритмы Дейкстры, Прима

поддержание “топ-k” элементов

Базовые операции

heappush(h, x) добавляет элемент

heappop(h) извлекает минимум

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

Пример:

Как сделать “максимальную кучу”

Частый трюк: хранить отрицания.

Ссылка:

heapq

!Схематичное сравнение основных структур данных и их типичных операций

Как выбирать структуру данных под задачу

Ниже — практическая “шпаргалка” выбора.

нужен порядок и индексы: list

нужен неизменяемый “пакет значений”: tuple

нужен быстрый поиск по ключу и хранение связанной информации: dict

нужен быстрый тест принадлежности и уникальность: set

нужна очередь/BFS/быстро с двух концов: deque

нужен минимум/приоритеты: heapq

Python-нюансы, которые влияют на алгоритмы

Итерация по list быстрее, чем ручная индексация в стиле for i in range(len(a)), но это зависит от того, нужен ли вам индекс.

Операция x in dict проверяет ключи, а не значения.

Сортировка в Python стабильна: элементы с равными ключами сохраняют относительный порядок.

Для “топ-k” часто выгоднее heapq, чем сортировать весь массив.

Ссылки:

sort (метод списка)

Краткое резюме

list — динамический массив: быстрый доступ по индексу, но медленные операции в начале.

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

dict — хеш-таблица ключ→значение, базовый инструмент для быстрых отображений и частот.

set — множество для уникальности и быстрого in.

deque — очередь/дек с операциями на концах.

heapq — приоритетная очередь с на вставку и извлечение минимума.

Поиск и сортировка: классические алгоритмы

Как тема связана с предыдущими статьями

В предыдущих статьях мы:

научились оценивать сложность через и понимать, почему выбор алгоритма важнее микрооптимизаций

разобрали базовые структуры данных Python (list, dict, set, deque, heapq) и типичные операции над ними

Теперь логичный следующий шаг — поиск и сортировка:

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

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

Поиск

Линейный поиск

Линейный поиск — это просмотр элементов по одному, пока не найдём нужный.

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

идея: пройти слева направо и сравнить каждый элемент с целью

Время работы:

худший случай: , где — количество элементов

лучший случай: , если нужное значение стоит первым

Пример:

Практический комментарий:

выражение target in a для list тоже делает линейный поиск и имеет сложность

Бинарный поиск

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

Идея бинарного поиска:

берём середину диапазона

сравниваем с искомым

отбрасываем половину диапазона

повторяем, пока диапазон не станет пустым

Время работы:

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

!Иллюстрация того, как бинарный поиск сужает диапазон

#### Бинарный поиск на точное совпадение

Что важно понимать в этой реализации:

left и right задают текущий допустимый диапазон индексов

mid всегда внутри диапазона

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

#### Поиск границы: первый элемент не меньше x (lower bound)

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

Типичная формулировка:

найти минимальный индекс i, такой что a[i] >= x

Это особенно полезно для:

подсчёта количества элементов в диапазоне

поиска первого подходящего значения

работы с повторами

Реализация:

Как читать результат:

функция возвращает индекс i в диапазоне от 0 до len(a)

если все элементы меньше x, вернётся len(a)

#### Модуль bisect

В Python есть готовая реализация бинарного поиска границ:

bisect_left(a, x) возвращает позицию вставки слева, то есть аналог lower_bound

bisect_right(a, x) возвращает позицию вставки справа, то есть индекс после последнего элемента <= x

Ссылка:

bisect — Array bisection algorithm

Пример: количество элементов, равных x в отсортированном массиве a:

Сортировка

Зачем сортировка так часто встречается в алгоритмах

Сортировка сама по себе — частая цель, но ещё чаще она выступает как шаг, который открывает более эффективные решения.

После сортировки становятся проще:

поиск через бинарный поиск

обработка повторов (сгруппировать одинаковые рядом)

задачи на пары и интервалы (часто решаются после сортировки)

Встроенная сортировка в Python

В Python есть две основные формы:

sorted(iterable, key=..., reverse=...) возвращает новый список

a.sort(key=..., reverse=...) сортирует список на месте и возвращает None

Ссылки:

sorted

list.sort

#### Сложность

Для сортировки сравнениями типичная оценка:

по времени

Здесь:

— число элементов

отражает количество уровней “деления” в эффективных стратегиях сортировки

Практическое замечание:

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

#### Стабильность сортировки

Сортировка в Python стабильна:

если два элемента равны по ключу сортировки, их исходный относительный порядок сохраняется

Почему это полезно:

можно сортировать по нескольким критериям в несколько проходов

можно не бояться, что “равные” элементы случайно перемешаются

#### key вместо “компаратора”

В Python сортировку обычно настраивают через key — функцию, которая возвращает ключ сравнения.

Пример сортировки строк по длине:

Пример сортировки по двум ключам: сначала по возрасту, потом по имени:

Классические алгоритмы сортировки: идеи и оценки

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

| Алгоритм | Идея | Время (типично) | Память (доп.) | Комментарий | |---|---|---:|---:|---| | Пузырьковая | много проходов, “всплытие” больших | | | учебная, почти не применяется | | Выбором | находим минимум и ставим на место | | | проста, но медленная | | Вставками | вставляем очередной элемент в отсортированную часть | , но быстро на почти отсортированных | | хороша для маленьких массивов | | Слиянием | делим пополам и сливаем отсортированные части | | | предсказуемая, часто стабильная | | Быстрая | разбиение по опорному элементу | в среднем | зависит от реализации | худший случай возможен | | Кучей | строим кучу и извлекаем минимум/максимум | | | предсказуемо, но больше константы |

Главные выводы из таблицы:

сортировки подходят только для небольших

— стандарт для больших входов

иногда мы выбираем алгоритм из-за памяти или гарантий худшего случая

Сортировки “не сравнениями”: когда можно быстрее

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

Самый известный пример — сортировка подсчётом:

работает быстро, если значения — целые числа из небольшого диапазона

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

Практическая идея:

если значения лежат в диапазоне 0..K, можно посчитать частоты и восстановить отсортированный массив

Важно:

этот подход полезен, когда невелик по сравнению с

если диапазон огромный, память и время на массив частот становятся проблемой

Практические паттерны задач

“Отсортируй и сделай быстро”

Частый приём:

сначала сортируем массив

потом решаем задачу за один проход или за логарифмы

Примеры того, что часто становится проще после сортировки:

удаление дублей

поиск ближайших элементов

задачи на пары (например, “найти два числа с суммой ”) через два указателя

Поиск по ответу через бинарный поиск

Бинарный поиск применяют не только к массиву, но и к ответу:

если можно проверить, “подходит ли” некоторое значение x за

и если условие монотонно (например, “для малых x не подходит, для больших подходит”)

тогда можно бинарным поиском найти минимальный или максимальный подходящий x

Этот паттерн встречается в задачах про:

минимальную скорость

минимальный размер

минимальное время

Python-нюансы, которые влияют на решения

list.sort() меняет список на месте и возвращает None, это помогает не писать лишних копий

sorted() удобен, когда нужно сохранить исходные данные

key обычно предпочтительнее любых “сложных сравнений”, потому что сортировка эффективно работает с ключами

для границ используйте bisect_left и bisect_right, чтобы не писать однотипный код и не ошибаться в условиях

Краткое резюме

линейный поиск: простой, но

бинарный поиск: , но требует отсортированных данных; особенно полезен для поиска границ

в Python для границ есть модуль bisect

сортировка в Python быстрая, стабильная, поддерживает key и обычно даёт

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

Рекурсия и методы «разделяй и властвуй»

Связь с предыдущими темами курса

Ранее мы разобрали:

как оценивать эффективность алгоритмов через

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

базовые алгоритмы поиска и сортировки, включая бинарный поиск и встроенную сортировку

В этой статье мы соберём это в более мощный подход:

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

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

Что такое рекурсия

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

Почти всегда рекурсивное решение состоит из двух частей:

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

рекурсивный шаг: как свести задачу размера к одной или нескольким задачам меньшего размера

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

Стек вызовов: что происходит в Python

Когда функция вызывает другую функцию (в том числе саму себя), Python хранит информацию о текущем состоянии в стеке вызовов:

локальные переменные

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

промежуточные значения

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

!Иллюстрация того, как рекурсивные вызовы накапливаются и затем «разворачиваются»

Ограничение глубины рекурсии

В CPython есть ограничение на глубину рекурсии (чтобы не переполнить стек). Иногда его можно увеличить, но делать это нужно осторожно.

узнать/изменить лимит можно через sys.getrecursionlimit() и sys.setrecursionlimit()

Ссылка: sys — System-specific parameters and functions

Важно:

увеличение лимита не делает рекурсию безопасной

если вы сильно увеличите лимит, можно получить падение интерпретатора из-за переполнения стека на уровне ОС

Простой пример: факториал

Факториал (обозначается ) — произведение чисел от до .

символ — входной размер (целое число)

символ — математическое обозначение факториала

Определение через рекурсию:

базовый случай: и

рекурсивный шаг:

Здесь:

— текущее число

— меньшая задача

— умножение

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

Типичные ошибки при рекурсии

нет базового случая

базовый случай есть, но до него нельзя дойти (задача не уменьшается)

“уменьшение” не гарантирует прогресс (например, случайные переходы)

рекурсия слишком глубокая для Python

Как оценивать сложность рекурсивных алгоритмов

У рекурсивного алгоритма удобно думать о двух вещах:

глубина рекурсии: сколько уровней вложенных вызовов будет

работа на уровне: сколько операций выполняется на каждом уровне

Пример:

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

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

Идея «разделяй и властвуй»

Разделяй и властвуй — стратегия проектирования алгоритмов:

разделить задачу на несколько подзадач меньшего размера

решить подзадачи (часто рекурсивно)

объединить ответы

Классический шаблон:

Divide: разбить вход на части

Conquer: решить части

Combine: объединить результаты

Эта стратегия естественно выражается рекурсией.

Бинарный поиск как «разделяй и властвуй»

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

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

каждый шаг сокращает диапазон примерно в 2 раза

значит, число шагов порядка

Сортировка слиянием: ключевой пример «разделяй и властвуй»

Сортировка слиянием (merge sort) работает так:

делим массив на две половины

сортируем каждую половину

сливаем две отсортированные половины в один отсортированный массив

!Как сортировка слиянием делит массив и затем собирает его обратно

Реализация на Python

Ниже учебная реализация (не самая быстрая по константам, но прозрачная по идее).

Почему сложность

У этой сортировки есть два ключевых факта:

глубина разбиения примерно

- здесь — число элементов массива - — “сколько раз можно делить пополам”, пока не останутся одиночные элементы

на каждом уровне мы в сумме “сливаем” все элементы один раз, то есть делаем работы

Итого получается порядка .

Память

Типичная реализация merge sort требует дополнительной памяти , потому что мы создаём новый массив при слиянии.

Быстрая сортировка: идея и практические нюансы

Быстрая сортировка (quicksort) тоже следует стратегии «разделяй и властвуй»:

выбираем опорный элемент

разделяем массив на элементы меньше/равные/больше опорного

рекурсивно сортируем части

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

В Python важно помнить:

рекурсивный quicksort легко упирается в ограничение глубины рекурсии

встроенная сортировка list.sort() почти всегда лучше в реальном коде

Ссылка: Sorting HOW TO

Когда рекурсия особенно полезна

Рекурсия хорошо подходит, когда структура задачи естественно рекурсивна:

«разделяй и властвуй» (merge sort, некоторые задачи на отрезках)

обходы деревьев (в следующих модулях курса)

перебор с возвратом (backtracking) в комбинаторных задачах

Когда лучше избегать рекурсии в Python

В Python часто выбирают итеративный подход, если:

возможна глубина в десятки тысяч и больше

можно явно хранить стек в list/deque

важно снизить накладные расходы на вызовы функций

При этом рекурсия остаётся отличным инструментом для ясного описания идеи — особенно на этапе проектирования.

Оптимизация рекурсивных вычислений: кэширование результатов

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

В Python есть готовый декоратор functools.lru_cache.

Ссылка: functools — Higher-order functions and operations on callable objects

Пример:

Замечание по месту в курсе:

сам приём кэширования мы ещё будем подробно обсуждать в темах про динамическое программирование

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

Краткое резюме

рекурсия строится из базового случая и рекурсивного шага

рекурсия использует стек вызовов и ограничена по глубине в Python

«разделяй и властвуй» делит задачу на части, решает их и объединяет

бинарный поиск и сортировка слиянием — классические примеры этой стратегии

merge sort даёт предсказуемую сложность , но требует доп. память

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

Графы: обходы, кратчайшие пути и MST

Как тема связана с предыдущими статьями

Ранее в курсе мы разобрали:

оценку сложности через и почему она определяет выбор подхода

базовые структуры данных Python (list, dict, set, deque, heapq)

поиск/сортировку и рекурсию как основу многих алгоритмических стратегий

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

обходы (BFS/DFS)

кратчайшие пути (BFS для невзвешенных, Дейкстра для неотрицательных весов)

минимальное остовное дерево (MST: Краскал/Прим)

Что такое граф

Граф — это набор:

вершин (узлов)

рёбер (соединений между вершинами)

Варианты графов:

неориентированный: ребро соединяет вершины в обе стороны

ориентированный: ребро имеет направление

взвешенный: у ребра есть вес (стоимость, длина, время)

невзвешенный: все рёбра считаются одинаковыми по “цене”

Обозначения, которые часто используют в оценках сложности:

— число вершин (от слова vertices)

— число рёбер (от слова edges)

!Наглядное сравнение ориентированного/неориентированного и взвешенного/невзвешенного графа

Как хранить граф в Python

Список рёбер

Храним рёбра как тройки (u, v, w) или пары (u, v).

удобно для алгоритмов типа Краскала (MST)

неудобно для частых “кто соседи у вершины?”

Матрица смежности

Это таблица , где mat[u][v] показывает наличие ребра или его вес.

быстрые проверки ребра

память , что плохо для больших разреженных графов

Список смежности (главный вариант в алгоритмах)

Для каждой вершины храним список её соседей.

память

обход соседей естественный и быстрый

Типичная структура:

невзвешенный граф: g[u] = [v1, v2, ...]

взвешенный граф: g[u] = [(v1, w1), (v2, w2), ...]

Пример построения списка смежности для неориентированного взвешенного графа:

Обходы графа

Обход нужен, чтобы “посетить” все достижимые вершины, а также чтобы строить расстояния, компоненты связности, деревья обхода.

Ключевая идея обоих обходов:

мы храним множество visited, чтобы не ходить по циклам бесконечно

BFS: поиск в ширину

BFS (Breadth-First Search) идёт “слоями” от стартовой вершины.

Свойство BFS:

в невзвешенном графе BFS находит кратчайшее число рёбер от старта до каждой вершины

Структура данных:

очередь collections.deque (потому что popleft() делает )

Сложность:

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

память O(|V| + |E|)O(|V|)O((|V| + |E|) \log |V|)O(|V|)

Здесь появляется из-за операций heappush/heappop: они работают примерно за , потому что высота кучи растёт как логарифм от числа элементов.

Полезные ссылки:

heapq — Heap queue algorithm

Что делать, если есть отрицательные веса

Если в графе встречаются отрицательные веса, Дейкстра не подходит. Классический алгоритм для таких случаев — Беллман–Форд.

Практическая заметка для курса:

Беллман–Форд проще по идее, но медленнее: обычно

его полезно знать как “страховку” для задач с отрицательными рёбрами и для обнаружения отрицательных циклов

Если в задаче явно сказано “веса неотрицательные”, берите Дейкстру.

Минимальное остовное дерево (MST)

Термины: остов и MST

Для неориентированного графа:

остовное дерево — это набор рёбер, который соединяет все вершины и не содержит циклов

минимальное остовное дерево (MST, Minimum Spanning Tree) — остовное дерево с минимальной суммой весов

Важно:

MST существует, если граф связный (иначе получится “минимальный остовный лес” по компонентам)

MST не ищет путь между двумя вершинами, это другая задача (это про “дешево соединить всех со всеми”)

!Пример графа и выделенного минимального остовного дерева

Алгоритм Краскала

Идея Краскала:

сортируем все рёбра по весу

идём от меньших к большим

берём ребро, если оно не создаёт цикл

Чтобы быстро проверять “создаст ли ребро цикл”, используют DSU (Disjoint Set Union), он же Union-Find:

find(x) возвращает представителя множества (компоненты)

union(a, b) объединяет два множества

Сложность:

основная стоимость — сортировка рёбер:

операции DSU работают очень быстро (почти константно на практике)

Реализация:

Когда Краскал особенно удобен:

когда граф задан списком рёбер

когда рёбер не слишком много и сортировка приемлема

Алгоритм Прима

Идея Прима:

начинаем с одной вершины

на каждом шаге добавляем самое дешёвое ребро, которое ведёт из уже построенной части MST наружу

Для эффективности используют приоритетную очередь (heapq).

Сложность со списком смежности и кучей:

время

память O(|V| + |E|)O(|V| + |E|)O(|V| + |E|)O((|V| + |E|) \log |V|)O(|E| \log |E|)O(|E| \log |V|)$) в неориентированном взвешенном графе.

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

Как тема связана с предыдущими статьями курса

Ранее в курсе мы разобрали:

оценку сложности через и практическую интерпретацию времени/памяти

базовые структуры данных Python (list, dict, set, deque, heapq)

сортировку и бинарный поиск как универсальные инструменты

рекурсию и «разделяй и властвуй»

графовые алгоритмы, где многие решения строятся на очередях, стеках и приоритетных очередях

Теперь мы переходим к двум стратегиям, которые встречаются чаще всего в задачах среднего и продвинутого уровня:

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

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

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

Динамическое программирование

Интуиция DP

DP применяют, когда выполняются две идеи:

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

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

Проще всего думать так:

мы выбираем, что именно будем запоминать

один раз считаем это значение для каждого состояния

используем сохранённое, когда оно снова нужно

Термины DP простыми словами

состояние: “точка” задачи, для которой мы хотим знать ответ (например, индекс i, сумма s, позиция в матрице (r, c))

dp-таблица: структура, где хранится ответ для каждого состояния (список, словарь, матрица)

переход: правило, как выразить dp[state] через более простые состояния

база: состояния, ответ для которых очевиден без переходов

!Пример dp-таблицы на сетке и направление вычисления

Два стиля реализации: memoization и tabulation

#### Memoization (рекурсия + кэш)

Идея:

пишем рекурсивную функцию

кэшируем результаты, чтобы не пересчитывать

В Python стандартный инструмент — functools.lru_cache.

Ссылка: functools.lru_cache

Плюсы:

код часто ближе к математическому определению

вычисляются только реально нужные состояния

Минусы:

риск упереться в глубину рекурсии

накладные расходы на рекурсивные вызовы

#### Tabulation (итеративно, снизу вверх)

Идея:

создаём dp-таблицу

заполняем её в порядке, при котором зависимости уже посчитаны

Плюсы:

надёжно по глубине стека

обычно быстрее в Python из-за отсутствия рекурсии

Минусы:

иногда сложнее подобрать порядок заполнения

можно посчитать лишние состояния

Пример: числа Фибоначчи (почему кэш важен)

Наивная рекурсия для Фибоначчи пересчитывает одни и те же значения много раз. DP устраняет повторы.

#### Вариант с lru_cache

Почему это DP:

состояние: n

база: n = 0, 1

переход: значение для n выражается через n-1 и n-2

Пример: минимум монет для суммы

Постановка:

даны номиналы монет coins

нужно набрать сумму S

найти минимальное число монет

Состояние:

dp[s] — минимальное число монет для суммы s

Переход можно записать формулой:

Расшифровка каждого элемента:

— текущая сумма, для которой мы считаем ответ

— один из номиналов монет

условие означает, что мы можем взять монету и остаться в допустимой сумме

— лучший ответ для “оставшейся” суммы

— потому что мы добавили одну монету

— выбираем вариант с наименьшим количеством монет

Итеративная реализация:

Оценка:

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

память:

DP на сетке: количество путей

Постановка:

есть сетка n x m

из клетки можно идти только вправо или вниз

нужно посчитать число способов добраться из (0, 0) в (n-1, m-1)

Идея DP:

dp[r][c] — число способов попасть в клетку (r, c)

в (r, c) можно прийти либо сверху (r-1, c), либо слева (r, c-1)

Формула:

Расшифровка:

— индекс строки

— индекс столбца

— способы прийти сверху

— способы прийти слева

сумма, потому что это два непересекающихся набора путей

Код (без препятствий):

Оптимизация памяти: “перекатывающийся” массив

Во многих DP по сетке или по двум индексам значение dp зависит только от предыдущей строки (или предыдущего “слоя”). Тогда можно хранить не всю таблицу, а только текущую и предыдущую строки.

Пример для сетки (память вместо ):

Почему это работает:

row[c] в момент обновления уже содержит “сверху” (предыдущую строку)

row[c-1] — это “слева” в текущей строке

Типичные ошибки в DP

неправильное определение состояния (не хватает информации, чтобы сделать корректный переход)

неверная база (dp стартует “не с того”)

неверный порядок заполнения в tabulation (используются ещё не посчитанные значения)

слишком большое число состояний (DP не проходит по времени/памяти)

попытка хранить огромную таблицу там, где нужна оптимизация памяти

Жадные алгоритмы

Интуиция жадного выбора

Жадный алгоритм строит решение шаг за шагом, каждый раз выбирая действие, которое выглядит “лучшим прямо сейчас”.

Примеры “жадного выбора”:

взять самый дешёвый доступный элемент

выбрать интервал, который заканчивается раньше всех

взять ребро минимального веса, если оно не создаёт цикл (Краскал)

Жадность часто даёт:

простую реализацию

быструю работу (нередко из-за сортировки)

Но ключевая проблема:

жадность не гарантирует оптимальность без доказательства

!Контраст: где жадность работает и где ломается

Когда жадный алгоритм корректен

Обычно нужно обосновать (на уровне идеи) одно из двух:

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

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

Это не формальность: без этого легко получить красивый и неправильный алгоритм.

Классический пример: выбор максимального числа непересекающихся интервалов

Задача:

есть интервалы на прямой

нужно выбрать как можно больше интервалов, которые не пересекаются

Правильная жадная стратегия:

отсортировать интервалы по правому концу

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

Код:

Почему работает (идея доказательства):

если взять интервал с минимальным концом, мы “оставляем максимум места” для следующих интервалов

любое оптимальное решение можно преобразовать так, чтобы первый выбранный интервал имел минимальный возможный конец

Жадность в графах: связь с предыдущей статьёй

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

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

Краскал: берём рёбра по возрастанию веса, не создавая цикл

Прим: всегда добавляем самое дешёвое ребро из построенной части наружу

Общий мотив:

правильный выбор структуры данных (например, heapq для минимума) делает жадный шаг эффективным

Ссылка на инструмент: heapq

Где жадность часто ломается

Самый частый сценарий:

задача похожа на “оптимизацию”

локально лучший шаг мешает глобальному оптимуму

Пример (минимум монет):

номиналы 1, 3, 4

сумма 6

Жадный выбор “брать самую большую монету” даёт:

(3 монеты)

Но оптимум:

(2 монеты)

Вывод:

жадный алгоритм для монет работает не всегда

DP для минимума монет работает всегда (в рамках ограничений по времени/памяти)

DP против жадности: как выбирать подход

Практическая таблица выбора

| Признак | Чаще подходит | Почему | |---|---|---| | Есть много вариантов, и “лучшее сейчас” может помешать будущему | DP | DP перебирает варианты через состояния | | Есть сильная монотонность/“лучший локальный шаг всегда безопасен” | Жадный | Можно доказать обменным аргументом | | Нужно не только оптимальное значение, но и восстановление решения | Оба | В DP обычно храним parent, в жадном — выбор на каждом шаге | | Ограничения большие, а структура задачи простая | Жадный | Часто (сортировка) | | Подзадачи повторяются многократно | DP | Кэширование даёт огромный выигрыш |

Мини-шпаргалка проектирования DP

Определите состояние: что должно быть известно, чтобы продолжать строить решение.

Определите базу: для каких состояний ответ очевиден.

Определите переход: как получить ответ из меньших состояний.

Проверьте порядок вычисления (если делаете tabulation).

Оцените число состояний и стоимость перехода.

Подумайте об оптимизации памяти.

Python-нюансы для DP и жадных решений

Для DP с целочисленными индексами часто быстрее список, чем словарь.

Если состояния “разреженные” (например, dp[(i, j)] встречается редко), удобнее dict.

Для memoization используйте lru_cache, но следите за глубиной рекурсии.

В жадных алгоритмах почти всегда появляется сортировка и/или куча.

Для восстановления ответа в DP добавляйте массив “родителей” или храните решение вместе с оценкой.

Полезные ссылки:

Dynamic programming (Wikipedia)

Greedy algorithm (Wikipedia)

Sorting HOW TO

Краткое резюме

DP применяют, когда подзадачи пересекаются, и выгодно запоминать ответы.

DP строится из состояния, базы и перехода; реализуется через memoization или tabulation.

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

Жадные алгоритмы делают локально лучший шаг; они быстрые, но требуют доказательства корректности.

Многие графовые алгоритмы (Дейкстра, Прим, Краскал) — примеры жадного подхода в сочетании с heapq и сортировкой.

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

Практика: шаблоны задач, тестирование и оптимизация решений

Как эта тема связывает весь курс

В предыдущих модулях вы получили основные «кирпичи» алгоритмического решения на Python:

оценку сложности и умение прикидывать, пройдёт ли решение по времени и памяти

базовые структуры данных (list, dict, set, deque, heapq)

поиск и сортировку, включая бинарный поиск границ

рекурсию и «разделяй и властвуй»

ключевые графовые алгоритмы (BFS/DFS, Дейкстра, MST)

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

Теперь задача — научиться стабильно доводить решение до рабочего состояния:

быстро узнавать тип задачи и выбирать подходящий шаблон

писать реализацию без типичных ошибок на границах

тестировать так, чтобы ловить баги до отправки

оптимизировать именно то, что даёт реальный выигрыш

!Общий рабочий цикл от идеи до оптимизации

Универсальный рабочий процесс решения

Быстрый разбор условия

Держите в голове три вопроса:

Что является размером входа (например, — длина массива, и — вершины и рёбра в графе)? Здесь , , — это именно размеры данных, от которых зависит время.

Какие ограничения (например, почти всегда исключает )?

Что нужно вывести (число, путь, само множество элементов, минимальную стоимость)?

Выбор модели данных

последовательность чисел/строк → чаще всего массивные техники (сортировка, два указателя, префиксные суммы)

отношения «кто с кем связан» → граф (список смежности)

«минимум/максимум среди текущих кандидатов» → куча (heapq) или монотонная структура

«выбор из вариантов, подзадачи повторяются» → DP

Шаблоны задач, которые встречаются чаще всего

Префиксные суммы

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

Идея:

строим массив pref, где pref[i] — сумма первых i элементов

тогда сумма на полуинтервале [l, r) равна pref[r] - pref[l]

Шаблон:

Типовые задачи:

количество подотрезков с заданной суммой (часто вместе с dict частот)

быстрые ответы на множество запросов сумм

Полезный паттерн «сумма подотрезка через хеш-таблицу»:

Два указателя

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

Чаще всего это работает, когда:

массив отсортирован, и надо искать пары/тройки

либо есть монотонность условия при расширении/сужении окна

Пример: найти пару с суммой S в отсортированном массиве.

Скользящее окно

Скользящее окно — частный случай двух указателей: мы держим окно [l, r) и двигаем границы так, чтобы инвариант оставался верным.

Важно:

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

Пример: минимальная длина подотрезка с суммой не меньше K (для неотрицательных чисел).

!Схема того, как окно расширяется и сжимается

Типовая ошибка:

применять скользящее окно там, где числа могут быть отрицательными, и монотонность суммы ломается

Хеш-таблица для частот и «последнего вхождения»

dict и Counter — основной инструмент для задач вида:

посчитать частоты

проверить уникальность

хранить «последний индекс, где встречалось значение»

Пример: длина самой длинной подстроки без повторяющихся символов (скользящее окно + dict).

Монотонный стек

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

следующий больший элемент справа

предыдущий меньший элемент слева

ближайший элемент, нарушающий условие монотонности

Пример: следующий больший элемент справа (для каждого индекса).

Ключевая идея эффективности:

каждый индекс кладётся в стек один раз

и вынимается тоже максимум один раз

поэтому итог по времени линейный

«Бинарный поиск по ответу»

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

Подходит, если:

есть функция-проверка ok(x), которая говорит, подходит ли ответ x

условие монотонно: если ok(x) верно, то для всех больших (или меньших) x тоже верно

Шаблон:

Типовая ошибка:

неверные границы lo/hi (не гарантируют наличие ответа)

ok(x) слишком медленная, и тогда даже логарифм не спасает

Графовые «скелеты»

Чтобы не изобретать заново, держите минимальные версии.

BFS (невзвешенный кратчайший путь):

Дейкстра (неотрицательные веса):

Заметка:

проверка if d != dist[u]: continue обязательна, иначе куча разрастается «устаревшими» записями и вы теряете время

DP-шаблон: табуляция и восстановление ответа

DP часто выигрывает не только за счёт правильных переходов, но и за счёт аккуратной реализации.

Мини-шаблон:

dp[i] — лучшее значение для состояния i

parent[i] — откуда пришли, чтобы восстановить решение

Пример: восстановление пути (общая идея, независимо от задачи).

Практические советы:

если состояния плотные и индексируемые, список обычно быстрее словаря

если таблица большая, ищите возможность «перекатывающегося массива» (вы уже видели это в DP по сетке)

Тестирование: как ловить ошибки системно

Крайние случаи, которые стоит проверять почти всегда

пустые или минимальные входы (например, n = 0, n = 1)

все элементы одинаковые

строго возрастающие/убывающие данные

большие значения (риск переполнения не так актуален в Python, но актуален для времени)

отсутствие ответа (например, «пути нет», «невозможно набрать сумму»)

Ассерты и инварианты

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

Пример: после сортировки массив должен быть неубывающим.

Важно:

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

Стресс-тест: рандом + брутфорс

Один из самых надёжных способов найти баг:

написать быстрое «правильное, но медленное» решение (брутфорс)

написать быстрое решение

генерировать много случайных тестов малого размера

сравнивать ответы и при расхождении печатать контрпример

Мини-шаблон:

Эта техника особенно полезна для:

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

DP с нетривиальными переходами

задач на графы (на маленьких графах можно брутфорсить)

Минимальная автоматизация тестов

Стандартные варианты:

модуль unittest: unittest — Unit testing framework

pytest: pytest

Если вы хотите тестировать свой код «как библиотеку», pytest часто удобнее.

Для более «математических» свойств бывает полезно property-based тестирование:

Hypothesis

Измерение и оптимизация: что реально помогает

Сначала асимптотика, потом константы

Если решение не проходит по времени, самый частый порядок действий:

переоценить сложность: нет ли скрытого (например, x in list внутри цикла)

подобрать другой алгоритм (сортировка + два указателя, хеш-таблица, куча, DP)

только после этого думать о микрооптимизациях

Чем измерять время

микробенчмарки отдельных кусочков: timeit

профилирование программы по функциям: cProfile

высокоточные замеры стендового времени: time.perf_counter

Пример cProfile (идея запуска):

Как это читать:

вы ищете функции, где суммарно тратится больше всего времени

затем оптимизируете алгоритм или структуру данных именно там

Быстрый ввод-вывод для больших данных

Если вход большой, используйте чтение из буфера:

Документация:

sys.stdin

Вывод большого количества строк часто ускоряют через накопление:

Документация:

sys.stdout

Память: как понять, куда она уходит

Для диагностики памяти полезен модуль:

tracemalloc

Общий принцип оптимизации памяти:

избегать лишних копий списков (например, срезов в горячем цикле)

не хранить то, что можно восстановить на лету

в DP по возможности «сжимать» измерения (перекатывающиеся массивы)

Python-нюансы, которые часто дают заметный эффект

заменять list.pop(0) на deque.popleft()

переносить проверки принадлежности из списка в set/dict

не сортировать внутри цикла, если можно отсортировать один раз

в графах хранить список смежности, а не матрицу, если граф разреженный

Ссылки по структурам данных:

collections.deque

heapq

Финальный чеклист перед отправкой решения

корректно обработаны минимальные размеры входа

корректно обработан случай «ответа нет»

нет скрытых вложенных линейных операций (например, in по списку в цикле)

используются правильные структуры данных (deque для очереди, heapq для минимума)

решение протестировано на ручных крайних случаях

по возможности сделан стресс-тест на маленьких данных

Краткое резюме

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

Тестирование в алгоритмах — это комбинация крайних случаев, инвариантов (assert) и стресс-теста (рандом + брутфорс).

Оптимизация начинается с выбора алгоритма и структуры данных, а измерения времени делают через timeit и cProfile.

Для больших входов важны ввод-вывод и отсутствие лишних копий данных.