Сложность алгоритмов (Big O) ⚡
Двадцать пять уроков подряд ты учился рассуждать о неопределённости: строил доверительные интервалы, проверял гипотезы, сравнивал группы через ANOVA, искал связь категориальных признаков через критерий хи-квадрат. Это был язык данных — то, как устроен мир чисел, который ты анализируешь. Начиная с этого урока курс поворачивает в другую сторону: туда, где данные не просто существуют, а хранятся, перебираются, сортируются и обрабатываются кодом. Это язык алгоритмов и структур данных — фундамент, без которого статистика и машинное обучение остаются красивой математикой на бумаге, но не работающим продуктом.
Представь конкретную ситуацию. Ты обучил модель эмбеддингов и хочешь для каждого пользователя найти сто самых похожих на него по вкусам — классическая задача рекомендательной системы. Самое наивное решение: для каждого пользователя посчитать расстояние до всех остальных и отсортировать. Если пользователей тысяча, это происходит мгновенно — компьютер и не заметит. Если пользователей миллион, тот же самый код, тот же алгоритм, только с другим числом на входе, будет работать не в тысячу раз дольше, а в миллион раз дольше — потому что операций там не миллион, а триллион. Разница между «мгновенно» и «никогда не дождёшься» здесь не в железе и не в языке программирования. Она — в том, как растёт количество работы алгоритма при росте размера входа. Именно это и называется сложностью алгоритма, а язык, на котором её описывают, — это нотация O-большое, Big O.
Здесь важно сразу отделить одну идею от другой: точное число секунд, за которое отработает код, зависит от процессора, языка, загруженности сервера — от всего, что к самому алгоритму отношения не имеет. А вот то, как это время растёт при увеличении входных данных в два, в десять, в миллион раз, — это уже свойство самого алгоритма, а не железа. Big O — способ отбросить всё несущественное (константы, детали реализации, скорость конкретного компьютера) и оставить главное: форму роста. Ты уже встречал похожую идею в курсе математического анализа, когда сравнивал бесконечно малые и вводил символы $o$ и $O$ Ландау для описания поведения функций при $x \to 0$ или $x \to \infty$. Здесь та же математическая конструкция применяется к другой задаче — не к пределам непрерывных функций, а к росту количества операций дискретного алгоритма при $n \to \infty$, где $n$ — размер входных данных. Идея настолько универсальна, что перекочевала из чистой математики прямиком в инженерную практику.
Этот урок открывает новый блок курса — структуры данных и алгоритмы. Дальше пойдут массивы и списки, стеки и очереди, хэш-таблицы, деревья и графы, алгоритмы сортировки и поиска. Но у всех этих тем есть общий язык оценки: любую структуру данных и любой алгоритм сравнивают именно через сложность по времени и по памяти. Не выучив этот язык сейчас, ты не сможешь содержательно читать таблицу «доступ — O(1), вставка — O(n)» дальше в курсе — она останется набором магических символов. Поэтому сегодня — только про то, как эти символы читать, писать и получать самостоятельно.
🎯 Ты узнаешь:
- Что такое временная и пространственная сложность алгоритма и почему их измеряют не в секундах, а в количестве операций относительно размера входа
- Как формально устроена нотация O-большое и как доказать, что конкретная функция принадлежит конкретному классу роста
- Шесть базовых классов сложности — от O(1) до O(2ⁿ) — с разбором конкретного кода и с таблицей, наглядно показывающей разницу в числах
- Практические правила определения сложности по структуре кода: циклы, вложенные циклы, последовательные блоки, рекурсия и рекуррентные соотношения
- Что такое амортизированная сложность и почему
list.append()в Python в среднем работает за O(1), хотя иногда выполняет куда больше работы - Почему выбор алгоритма с правильной асимптотикой — это не теоретическое упражнение, а разница между работающим ML-пайплайном и падающим по таймауту сервисом
История: откуда взялась нотация O-большое
Символ $O$ появился в математике куда раньше, чем возникла информатика как дисциплина. В 1894 году немецкий математик Пауль Бахман в книге «Analytische Zahlentheorie» («Аналитическая теория чисел») ввёл обозначение $f(n) = O(g(n))$ для сравнения роста функций в задачах теории чисел — ему нужен был компактный способ сказать «эта функция растёт не быстрее, чем та, с точностью до постоянного множителя», не выписывая каждый раз громоздкие неравенства. Сама буква $O$ была выбрана не случайно: она от немецкого слова «Ordnung» — порядок, то есть порядок роста функции.
Настоящую популярность нотации принёс другой немецкий математик, Эдмунд Ландау, ученик и коллега многих ключевых фигур теории чисел начала XX века. Ландау систематически использовал символы $O$ и $o$ (о-малое) в своих работах и учебниках, благодаря чему они и получили второе имя — «символы Ландау». Ландау же явно сформулировал разницу между $O$ (верхняя граница роста с точностью до константы) и $o$ (строго более медленный рост, отношение стремится к нулю) — именно эта пара понятий и легла в основу более позднего университетского курса математического анализа, где ты уже встречал их при сравнении бесконечно малых.
В информатику асимптотическая нотация пришла заметно позже, в 1960–70-е годы, и её главным популяризатором стал Дональд Кнут — автор фундаментального многотомника «The Art of Computer Programming» («Искусство программирования») и один из основателей формального анализа алгоритмов как отдельной дисциплины. Кнут не просто заимствовал математический символ — он адаптировал его под нужды информатики, где алгоритмы часто удобнее описывать не одной точной границей, а тройкой понятий: $O$ (не хуже, чем...), $\Omega$ (не лучше, чем...) и $\Theta$ (точно как...). В 1976 году Кнут опубликовал отдельную статью «Big Omicron and big Omega and big Theta» («О-большое, Омега-большое и Тета-большое»), где навёл порядок в путанице, возникшей из-за того, что программисты и математики к тому моменту уже начали использовать $O$ вольно — то как верхнюю границу, то как точную асимптотику. С тех пор именно кнутовская тройка обозначений — стандарт, которым пользуется вся индустрия, от учебников до документации библиотек вроде numpy и scikit-learn, где рядом с названием метода нередко можно увидеть его вычислительную сложность именно в этой нотации.
Временная и пространственная сложность: что мы вообще измеряем
Интуиция
Когда говорят «этот алгоритм работает за 3 секунды», это почти бесполезная фраза: на другом процессоре будет 1 секунда, на слабом ноутбуке — 10, на другом языке программирования — вообще другое число. Секунды зависят от железа, компилятора, загрузки системы — от всего, кроме самого алгоритма. Чтобы сравнивать алгоритмы честно, отсчёт ведут не в секундах, а в количестве элементарных операций — присваиваний, сравнений, арифметических действий, — и смотрят, как это количество растёт с ростом размера входных данных $n$. Это и есть временная сложность.
Аналогично для памяти: вместо мегабайт, которые зависят от того, как именно язык программирования хранит объекты в памяти, считают, сколько дополнительных ячеек памяти (сверх самих входных данных) требуется алгоритму, и как это число растёт с ростом $n$. Это пространственная сложность.
Определение: Временная сложность алгоритма — функция $T(n)$, отражающая, как растёт число элементарных операций, выполняемых алгоритмом, в зависимости от размера входных данных $n$. Пространственная сложность $S(n)$ — функция, отражающая, как растёт объём дополнительной памяти (не считая память под сами входные данные), необходимой алгоритму, в зависимости от $n$.
Обрати внимание на слово «дополнительной» в определении пространственной сложности: массив из $n$ чисел на входе занимает память сам по себе, и это не заслуга и не недостаток алгоритма, который его обрабатывает. Считают именно то, что алгоритм выделяет сверх этого — временные переменные, вспомогательные структуры, стек вызовов при рекурсии.
Примеры с разбором
Пример 1 (простой): сумма элементов массива
def sum_array(arr):
total = 0 # 1 операция
for x in arr: # n итераций
total += x # 1 операция на итерацию
return total
Разбор. Инициализация total — одна операция. Цикл выполняется ровно $n$ раз, где $n$ — длина массива, и на каждой итерации одна операция сложения. Итого $T(n) \approx n + 1$ элементарных операций. Дополнительной памяти используется одна переменная total, независимо от размера массива, значит $S(n) = O(1)$ — константная память. Это классический линейный по времени, константный по памяти алгоритм.
Пример 2 (средний): поиск дубликатов наивным перебором пар
def has_duplicates(arr):
n = len(arr)
for i in range(n): # n итераций
for j in range(i + 1, n): # до n итераций
if arr[i] == arr[j]:
return True
return False
Разбор. Внешний цикл проходит по всем $n$ элементам. Для каждого значения $i$ внутренний цикл проверяет оставшиеся справа элементы — сначала $n-1$ сравнение, потом $n-2$, и так далее до нуля. Суммарное число сравнений: $(n-1) + (n-2) + \dots + 1 + 0 = \dfrac{n(n-1)}{2}$. Это квадратичная функция от $n$: при раскрытии скобок получаем $\dfrac{n^2 - n}{2}$, и при больших $n$ доминирует слагаемое $n^2/2$. Дополнительной памяти алгоритм не использует, кроме пары индексов, поэтому $S(n) = O(1)$, а по времени — квадратичный рост.
Пример 3 (сложный): рекурсивный и итеративный факториал
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1) # n вложенных вызовов
def factorial_iterative(n):
result = 1
for i in range(2, n + 1): # n итераций
result *= i
return result
Разбор. По времени обе версии эквивалентны: и рекурсивная, и итеративная выполняют $n$ умножений, значит $T(n) = O(n)$ у обеих. А вот по памяти они принципиально разные. Итеративная версия хранит одну переменную result — $S(n) = O(1)$. Рекурсивная версия на каждый вызов кладёт в стек вызовов новый «кадр» — адрес возврата, значение параметра n, локальные переменные, — и этот кадр не освобождается, пока не завершится самый глубокий вызов. Глубина рекурсии равна $n$, значит стек вызовов растёт линейно, $S(n) = O(n)$. Это ровно та причина, по которой в Python при больших $n$ рекурсивный факториал упадёт с RecursionError, а итеративный отработает без проблем: они одинаковы по времени, но принципиально разные по памяти.
Почему это важно
В машинном обучении временная и пространственная сложность решают, будет ли твой код вообще работать на реальных объёмах данных, а не только на игрушечном примере из ноутбука. Наивное вычисление попарных расстояний между объектами для поиска похожих — тот самый пример из вступления — имеет временную сложность $O(n^2 d)$, где $n$ — число объектов, а $d$ — размерность эмбеддинга: для каждой из примерно $n^2/2$ пар нужно посчитать расстояние по $d$ координатам. При $n = 10\,000$ это порядка $10^8$ операций — доли секунды. При $n = 1\,000\,000$ — уже порядка $10^{12}$ операций, и это не «в сто раз дольше», а недостижимо на практике в разумное время. Именно поэтому в промышленных системах поиска похожих объектов (рекомендательные системы, поиск по векторным базам данных, retrieval-компонент в RAG-системах) наивный перебор заменяют структурами вроде KD-деревьев, HNSW-графов или библиотек приближённого поиска ближайших соседей (FAISS, Annoy) — они меняют асимптотику с квадратичной на логарифмическую или почти линейную ценой небольшой потери точности. Понимание сложности — это ровно тот инструмент, который позволяет заранее посчитать «взлетит это на миллионе строк или нет», не дожидаясь зависшего сервера.
Нотация O-большое: формальный язык роста
Интуиция
Функция $T(n) = 3n^2 + 5n + 100$ — точное описание числа операций алгоритма. Но при $n = 1\,000\,000$ слагаемое $3n^2$ равно $3 \cdot 10^{12}$, слагаемое $5n$ — всего лишь $5 \cdot 10^6$, а $100$ и вовсе теряется на этом фоне. При больших $n$ поведение всей суммы практически полностью определяется старшим слагаемым — остальные становятся пренебрежимо малой добавкой. Нотация O-большое формализует именно эту интуицию: она отбрасывает младшие слагаемые и постоянные множители и оставляет только «форму» роста — то, что реально решает, взлетит алгоритм на больших данных или нет.
Определение
Определение: Говорят, что $f(n) = O(g(n))$, если существуют такие константы $c > 0$ и $n_0 \geq 0$, что для всех $n \geq n_0$ выполняется неравенство $f(n) \leq c \cdot g(n)$. Содержательно это значит: начиная с некоторого момента $n_0$, функция $f(n)$ растёт не быстрее, чем $g(n)$, умноженная на некоторую постоянную.
Важная деталь этого определения — оба параметра, $c$ и $n_0$, можно подбирать любыми, лишь бы неравенство выполнялось для всех $n$ от $n_0$ и дальше. Это делает $O$-нотацию нечувствительной к константам и к поведению функции на маленьких $n$ — она описывает только асимптотику, то есть предел поведения при $n \to \infty$.
По умолчанию, когда говорят «сложность алгоритма — $O(g(n))$» без уточнений, обычно имеют в виду сложность в худшем случае (worst case) — при самых неудачных для алгоритма входных данных. Кроме худшего случая существуют понятия сложности в лучшем случае (best case, обозначается через $\Omega$ — нижнюю границу) и в среднем случае (average case) — по всем возможным входам данного размера. Точная асимптотика, когда $f(n)$ одновременно является и верхней, и нижней границей с точностью до констант, обозначается $\Theta(g(n))$. В этом уроке фокус — на $O$, как на самой практически важной и распространённой оценке: она отвечает на вопрос «насколько плохо может быть», а именно это чаще всего интересует инженера, проектирующего систему, которая должна работать надёжно при любых входных данных.
Примеры с разбором
Пример 1 (простой): докажи, что $3n + 5 = O(n)$
Решение. Нужно подобрать $c$ и $n_0$ такие, что $3n + 5 \leq c \cdot n$ при всех $n \geq n_0$. Возьмём $c = 4$: неравенство $3n + 5 \leq 4n$ равносильно $5 \leq n$, то есть $n \geq 5$. Значит, при $c = 4$ и $n_0 = 5$ определение выполняется. Проверка на границе: при $n = 5$ левая часть $3 \cdot 5 + 5 = 20$, правая $4 \cdot 5 = 20$ — равенство, неравенство $\leq$ выполнено. При $n = 6$: $23 \leq 24$ ✓. Значит, $3n + 5 = O(n)$.
Пример 2 (средний): докажи, что $n^2 + 100n = O(n^2)$
Решение. Нужно найти $c$ и $n_0$ такие, что $n^2 + 100n \leq c \cdot n^2$ при $n \geq n_0$. Возьмём $c = 2$: неравенство $n^2 + 100n \leq 2n^2$ равносильно $100n \leq n^2$, то есть $100 \leq n$ (после деления обеих частей на $n > 0$). Значит, при $c = 2$, $n_0 = 100$ определение выполняется. Обрати внимание: слагаемое $100n$ — линейное, и на первый взгляд коэффициент $100$ выглядит внушительно, но начиная с $n = 100$ квадратичное слагаемое $n^2$ его полностью «перевешивает», а дальше — тем более. Это и есть суть асимптотики: она смотрит не на то, что происходит при маленьких $n$, а на предельное поведение.
Пример 3 (сложный): покажи, что $\log n = O(n)$, но $n \neq O(\log n)$
Решение. Первая часть: нужно найти $c, n_0$ такие, что $\log n \leq c \cdot n$ при $n \geq n_0$. Возьмём $c = 1$, $n_0 = 1$: для любого $n \geq 1$ верно $\log n \leq n$ (логарифм растёт заведомо медленнее линейной функции, это можно проверить прямой подстановкой: при $n=1$, $\log 1 = 0 \leq 1$; при $n=1000$, $\log_2 1000 \approx 10 \leq 1000$). Значит, $\log n = O(n)$ — верно.
Вторая часть — от противного. Допустим, что $n = O(\log n)$, то есть существуют $c, n_0$ такие, что $n \leq c \cdot \log n$ для всех $n \geq n_0$. Разделим обе части на $\log n$ (при $n > 1$ он положителен): получаем $\dfrac{n}{\log n} \leq c$ — то есть отношение должно быть ограничено постоянной константой $c$ при всех достаточно больших $n$. Но отношение $\dfrac{n}{\log n}$ неограниченно растёт при $n \to \infty$ (числитель растёт линейно, знаменатель — логарифмически, то есть сколь угодно медленнее): при $n = 1000$ это отношение около $100$, при $n = 10^6$ — уже около $50\,000$, при $n = 10^9$ — свыше двадцати миллионов. Ни одна константа $c$ не может ограничить сверху неограниченно растущую величину — противоречие. Значит, $n \neq O(\log n)$.
Ответ. $\log n = O(n)$ выполняется, но обратное неверно — это формальное доказательство интуитивно очевидного факта: логарифм растёт строго медленнее линейной функции, и с ростом $n$ разрыв между ними становится сколь угодно большим, а не постоянным.
Почему это важно
$O$-нотация — это общий язык, на котором инженеры из разных команд, использующие разные языки программирования и разное железо, могут сравнивать алгоритмы, не углубляясь в детали реализации. Когда в документации scikit-learn для метода KMeans написано, что сложность одной итерации — $O(n \cdot k \cdot d)$ (где $n$ — число объектов, $k$ — число кластеров, $d$ — размерность), это позволяет заранее, ещё до запуска, прикинуть, сколько времени займёт обучение на твоих данных, и сравнить K-means с альтернативами вроде иерархической кластеризации, у которой сложность заметно выше — $O(n^2 \log n)$ или $O(n^3)$ в зависимости от реализации. Без общего формального языка такое сравнение сводилось бы к «у меня на моём ноутбуке было быстрее» — утверждению, бесполезному для кого угодно, кроме автора этого ноутбука.
Основные классы сложности алгоритмов
Интуиция
Хотя теоретически функций сложности бесконечно много, на практике подавляющее большинство алгоритмов укладываются в несколько характерных классов, которые стоит знать «в лицо» и уметь узнавать по коду с первого взгляда. Разница между соседними классами кажется небольшой на маленьких $n$, но на реальных объёмах данных превращается в разницу между мгновенным ответом и вечным ожиданием. Взгляни на таблицу — она показывает число операций для разных классов сложности при разных $n$, если условно считать, что компьютер выполняет $10^8$ операций в секунду:
| $n$ | $O(1)$ | $O(\log n)$ | $O(n)$ | $O(n \log n)$ | $O(n^2)$ | $O(2^n)$ |
|---|---|---|---|---|---|---|
| $10$ | 1 | ~3 | 10 | ~33 | 100 | 1 024 |
| $100$ | 1 | ~7 | 100 | ~664 | 10 000 | $\approx 10^{30}$ |
| $1\,000$ | 1 | ~10 | 1 000 | ~9 966 | 1 000 000 | немыслимо много |
| $1\,000\,000$ | 1 | ~20 | 1 000 000 | ~20 000 000 | $10^{12}$ (~3 часа) | немыслимо много |
При $n = 1\,000\,000$ линейный алгоритм отработает за миллисекунды, а квадратичный на том же самом железе — уже несколько часов. Экспоненциальный алгоритм при $n$ больше пары сотен становится невозможно посчитать в принципе, даже если запустить его на всех компьютерах планеты одновременно — число операций превысит количество атомов в наблюдаемой Вселенной уже при относительно скромных $n$.
Определение
Определение: Основные классы сложности, упорядоченные по возрастанию роста: $O(1)$ — константная сложность (не зависит от $n$); $O(\log n)$ — логарифмическая; $O(n)$ — линейная; $O(n \log n)$ — линеарифмическая; $O(n^2)$ — квадратичная (частный случай полиномиальной сложности $O(n^k)$); $O(2^n)$ — экспоненциальная. Каждый следующий класс в этом списке растёт строго быстрее предыдущего при $n \to \infty$, и это можно строго доказать так же, как в примере с $\log n$ и $n$ выше.
Примеры с разбором
$O(1)$ — константная сложность.
def get_first(arr):
return arr[0] # всегда одна операция, независимо от len(arr)
Доступ к элементу массива по индексу не зависит от размера массива: что в массиве из 5 элементов, что в массиве из 5 миллионов, операция «взять элемент по известному индексу» занимает одно и то же время, потому что процессор вычисляет адрес ячейки напрямую по формуле, без перебора.
$O(\log n)$ — логарифмическая сложность.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Бинарный поиск в отсортированном массиве на каждом шаге отбрасывает половину оставшегося диапазона поиска. Если исходный диапазон — $n$ элементов, то после первого шага остаётся $n/2$, после второго — $n/4$, и так далее, пока не останется один элемент. Число шагов до этого момента — это степень, в которую нужно возвести $2$, чтобы получить $n$, то есть $\log_2 n$. При миллиарде элементов это всего около тридцати сравнений — вместо миллиарда при линейном переборе.
$O(n)$ — линейная сложность.
def linear_search(arr, target):
for i, x in enumerate(arr): # до n итераций
if x == target:
return i
return -1
Линейный поиск в неотсортированном массиве в худшем случае (искомого элемента нет или он последний) проверяет каждый элемент ровно один раз. Число операций растёт пропорционально $n$ — увеличил массив в десять раз, время выполнения выросло тоже примерно в десять раз.
$O(n \log n)$ — линеарифмическая сложность.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # T(n/2)
right = merge_sort(arr[mid:]) # T(n/2)
return merge(left, right) # O(n) на слияние
Сортировка слиянием на каждом уровне рекурсии выполняет слияние двух отсортированных половин за линейное время $O(n)$, а глубина рекурсии — $\log n$ уровней (массив делится пополам, пока не останутся единичные элементы). Итоговая сложность — произведение $n$ (работа на каждом уровне) на $\log n$ (число уровней), то есть $O(n \log n)$. Это тот самый класс, к которому относятся все эффективные алгоритмы сортировки сравнением, и это же нижняя теоретическая граница для сортировки сравнением в принципе — быстрее в общем случае не бывает.
$O(n^2)$ — квадратичная сложность.
def bubble_sort(arr):
n = len(arr)
for i in range(n): # n итераций
for j in range(n - i - 1): # до n итераций
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
Пузырьковая сортировка — классический пример квадратичной сложности: два вложенных цикла, каждый порядка $n$ итераций, дают порядка $n^2$ операций сравнения-обмена. К этому же классу относится наивное вычисление всех попарных расстояний между $n$ объектами, разобранное во вступлении.
$O(2^n)$ — экспоненциальная сложность.
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2) # два рекурсивных вызова
Наивный рекурсивный расчёт чисел Фибоначчи без запоминания промежуточных результатов на каждом шаге порождает два новых вызова, и дерево рекурсии растёт вдвое на каждый уровень глубины $n$ — итоговое число вызовов растёт как $2^n$ (точнее, как $\phi^n$, где $\phi \approx 1{,}618$ — золотое сечение, но по порядку роста это тот же экспоненциальный класс). При $n = 40$ это уже больше миллиарда вызовов; при $n = 50$ — время выполнения на обычном компьютере исчисляется часами, хотя сама задача — вычислить одно число Фибоначчи — тривиальна для итеративного алгоритма за $O(n)$.
Почему это важно
Разные классы сложности встречаются в машинном обучении на каждом шагу, и знание, к какому классу относится этап пайплайна, определяет, стоит ли вообще запускать его на реальном объёме данных. Инференс одного объекта через k-ближайших соседей наивным способом — $O(n \cdot d)$, где $n$ — размер обучающей выборки, а $d$ — число признаков: приемлемо для тысяч объектов, но уже проблематично для десятков миллионов без специальных структур ускоренного поиска. Обучение линейной регрессии методом нормальных уравнений — $O(n d^2 + d^3)$: слагаемое $d^3$ (обращение матрицы $d \times d$) становится критичным, когда признаков не десятки, а тысячи, — именно поэтому на многомерных данных предпочитают градиентный спуск с линейной по $d$ стоимостью одной итерации. Полный перебор подмножеств признаков для отбора «идеального» набора — классическая $O(2^d)$ задача: уже при тридцати признаках перебрать все возможные подмножества физически невозможно, и именно поэтому существуют жадные и приближённые методы отбора признаков вместо честного перебора.
Как определять сложность алгоритма по коду
Интуиция
Сложность алгоритма почти всегда можно определить, не запуская код и не измеряя время, а просто глядя на его структуру: сколько там циклов, вложены ли они друг в друга, есть ли рекурсия. Существует небольшой набор правил, которые покрывают подавляющее большинство практических случаев.
Определение
Определение (практические правила подсчёта): Для последовательных, не вложенных друг в друга блоков кода сложности складываются, а в асимптотике остаётся только максимальное (доминирующее) слагаемое: $O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))$. Для вложенных циклов сложности перемножаются: цикл на $n$ итераций, внутри которого цикл на $m$ итераций, даёт $O(n \cdot m)$. Для рекурсивных алгоритмов сложность описывается рекуррентным соотношением вида $T(n) = a \cdot T(n/b) + f(n)$, где $a$ — число рекурсивных вызовов, $n/b$ — размер подзадачи, а $f(n)$ — работа вне рекурсивных вызовов; такое соотношение решается разбором по так называемой основной теореме о рекуррентных соотношениях (master theorem).
Примеры с разбором
Пример 1 (простой): последовательные блоки разной сложности
def process(arr):
n = len(arr)
total = sum(arr) # O(n)
for i in range(n): # O(n)
for j in range(n): # O(n)
pass # итого O(n^2)
return total
Разбор. Первая строка — вызов sum(arr) — это линейный проход по массиву, $O(n)$. Дальше идёт двойной вложенный цикл — $O(n) \cdot O(n) = O(n^2)$. Эти два блока не вложены друг в друга, а идут последовательно, поэтому их сложности складываются: $O(n) + O(n^2)$. Асимптотически доминирует старшее слагаемое, поэтому итоговая сложность всей функции — $O(n^2)$: линейная часть тонет на фоне квадратичной при больших $n$, точно так же, как в примере с $3n^2 + 5n + 100$ выше.
Пример 2 (средний): вложенный цикл с зависимым диапазоном
def count_pairs(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(i, n): # диапазон зависит от i
count += 1
return count
Разбор. На первый взгляд может показаться, что раз внутренний цикл не всегда проходит все $n$ значений, сложность должна быть меньше квадратичной. Но при $i = 0$ внутренний цикл делает $n$ итераций, при $i = 1$ — $n - 1$, ..., при $i = n-1$ — одну итерацию. Суммарное число итераций — это уже знакомая нам сумма арифметической прогрессии $n + (n-1) + \dots + 1 = \dfrac{n(n+1)}{2}$, что асимптотически равно $O(n^2)$: коэффициент перед $n^2$ отличается (здесь он $1/2$, а не $1$), но константы в $O$-нотации не учитываются, и класс сложности остаётся квадратичным.
Пример 3 (сложный): тройной вложенный цикл — умножение матриц
def matmul(A, B, n):
C = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
return C
Разбор. Три вложенных цикла, каждый на $n$ итераций, дают перемножение трёх сложностей: $O(n) \cdot O(n) \cdot O(n) = O(n^3)$. Это классическая — «школьная» — сложность умножения квадратных матриц размера $n \times n$. При $n = 1000$ это уже порядка миллиарда операций. Существуют более быстрые алгоритмы умножения матриц (алгоритм Штрассена — $O(n^{2{,}807})$ и более поздние теоретические результаты с ещё меньшим показателем степени), но на практике для большинства размеров матриц библиотеки линейной алгебры (numpy, BLAS) используют вариации именно кубической схемы, сильно оптимизированные по константам и по использованию кэша процессора.
Пример 4 (сложный): анализ рекурсии через рекуррентное соотношение
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
Разбор. Каждый вызов делает $O(1)$ работы (сравнение и вычисление середины) и порождает ровно один рекурсивный вызов на половине оставшегося диапазона. Рекуррентное соотношение: $T(n) = T(n/2) + O(1)$. Раскроем его вручную: $T(n) = T(n/2) + c = T(n/4) + 2c = T(n/8) + 3c = \dots = T(1) + c \cdot \log_2 n$. Раскрытие останавливается, когда размер подзадачи достигает единицы, а это происходит ровно после $\log_2 n$ шагов деления пополам. Значит, $T(n) = O(\log n)$ — подтверждение того же результата, что мы получили для итеративной версии бинарного поиска, но теперь выведенное формально через анализ рекурсии, а не через интуицию «на каждом шаге отбрасываем половину».
Для сравнения — рекуррентное соотношение сортировки слиянием: $T(n) = 2T(n/2) + O(n)$ (два рекурсивных вызова на половинах плюс линейное слияние). По основной теореме о рекуррентных соотношениях: сравниваем $f(n) = n$ с $n^{\log_2 2} = n^1 = n$ — они совпадают по порядку роста, это второй случай теоремы, и решение — $T(n) = O(n \log n)$, что в точности совпадает с прямым рассуждением «работа на уровне, умноженная на число уровней» из предыдущего раздела.
Почему это важно
Умение читать сложность прямо по структуре кода — практический навык код-ревью, а не абстрактная теория. Одна из самых частых скрытых проблем в реальных ML-пайплайнах — случайно получившаяся квадратичная сложность там, где автор рассчитывал на линейную: например, накопление результатов в pandas.DataFrame через pd.concat() внутри цикла на каждой итерации создаёт новый объект и копирует уже накопленные данные заново, превращая линейный по своей сути процесс сборки таблицы в квадратичный по общему времени. Такой код долго остаётся незамеченным, потому что на небольших тестовых данных (сотни строк) он отрабатывает быстро, а падает по таймауту только на боевых объёмах — ровно та ловушка, о которой предупреждает вся эта тема.
Амортизированная сложность
Интуиция
Не все операции в реальных структурах данных стоят одинаково каждый раз. Иногда операция почти всегда дешёвая, но время от времени — редко, предсказуемо редко — она внезапно дорогая. Возьмём знакомый пример: список в Python. Добавление элемента в конец списка (list.append) в подавляющем большинстве случаев — это просто запись значения в уже выделенную ячейку памяти, $O(1)$. Но список хранится во внутреннем массиве фиксированного размера, и когда этот внутренний массив заполняется целиком, требуется выделить новый, больший массив (обычно вдвое больше) и скопировать в него все существующие элементы — операция стоимостью $O(n)$. Если оценивать сложность append только по этому редкому худшему случаю, придётся сказать «$O(n)$», что явно несправедливо описывает поведение списка на практике: подавляющее большинство вызовов дешёвые. Амортизированный анализ — это способ честно усреднить стоимость операции по длинной последовательности вызовов, чтобы учесть и частые дешёвые, и редкие дорогие случаи вместе.
Определение
Определение: Амортизированная сложность операции — это средняя стоимость одной операции в худшем случае, посчитанная по любой последовательности из $n$ таких операций: если суммарная стоимость $n$ операций ограничена сверху величиной $O(n \cdot f(n))$, то говорят, что амортизированная сложность одной операции — $O(f(n))$, даже если стоимость отдельных операций внутри последовательности сильно различается.
Ключевое отличие амортизированной сложности от «средней сложности» (average case): средняя сложность усредняет по случайности входных данных (какие данные подадут на вход), а амортизированная — по детерминированной последовательности операций над одной и той же структурой данных, без каких-либо предположений о случайности. Это гарантия, а не вероятностная оценка.
Примеры с разбором
Пример 1 (простой): динамический массив с удвоением ёмкости
Рассмотрим последовательность из $n$ операций append в изначально пустой динамический массив, который при заполнении удваивает свою ёмкость (ровно так устроен список в Python и std::vector в C++). Копирование происходит на вставках номер $1, 2, 4, 8, 16, \dots$ (каждый раз, когда число элементов становится степенью двойки), и стоимость копирования на шаге $2^k$ равна примерно $2^k$ операций.
Разбор. Суммарная стоимость всех операций копирования за $n$ вставок:
$$1 + 2 + 4 + 8 + \dots + 2^{\lceil \log_2 n \rceil} < 2n$$Это сумма геометрической прогрессии, и она меньше удвоенного последнего члена — известный факт, что сумма геометрической прогрессии со знаменателем $2$ асимптотически равна её последнему, самому большому слагаемому, умноженному на константу. Добавим к этому $n$ операций собственно записи новых элементов (каждая — $O(1)$), и суммарная стоимость всех $n$ вставок — $O(n) + O(n) = O(n)$. Разделив на число операций $n$, получаем амортизированную стоимость одной вставки — $O(1)$, несмотря на то, что отдельные вставки (на степенях двойки) стоят $O(n)$ каждая.
Пример 2 (средний): почему удвоение, а не увеличение на фиксированное число
Сравним стратегию удвоения ёмкости с альтернативной: увеличивать ёмкость каждый раз на фиксированную константу (например, на 10 элементов), а не в геометрической прогрессии.
Разбор. При увеличении на константу $k$ копирование будет происходить на вставках номер $k, 2k, 3k, \dots$ — то есть примерно $n/k$ раз, и стоимость каждого копирования линейно растёт с текущим размером: суммарная стоимость копирований — $k + 2k + 3k + \dots + (n/k) \cdot k \approx \dfrac{n^2}{2k}$. Это уже квадратичная суммарная стоимость, то есть амортизированная стоимость одной вставки — $O(n)$, а не $O(1)$. Разница принципиальная: именно геометрический рост ёмкости (удвоение или любой другой постоянный множитель больше единицы) гарантирует амортизированную константную стоимость вставки, а линейный рост ёмкости — нет. Это не деталь реализации, а математически необходимое условие, и именно поэтому все промышленные реализации динамических массивов растут геометрически.
Пример 3 (сложный): метод учётных монет для стека с операцией multipop
Рассмотрим стек с тремя операциями: push (добавить элемент, $O(1)$), pop (убрать верхний элемент, $O(1)$) и multipop(k) (убрать сразу $k$ верхних элементов, стоимость $O(\min(k, \text{размер стека}))$, если стек меньше $k$, снимаются все элементы). В худшем случае одна операция multipop может стоить $O(n)$, если стек глубокий. Оценим амортизированную стоимость последовательности из $n$ операций push, pop и multipop в произвольном порядке.
Разбор. Применим метод учётных монет: договоримся, что каждая операция push «платит» не одну условную монету, а две — одну за саму запись элемента, а вторую откладывает про запас на будущее удаление именно этого элемента. Тогда каждая операция pop (в том числе внутри multipop) не тратит новых ресурсов — она использует ранее отложенную монету. Поскольку каждый элемент может быть удалён (через pop или как часть multipop) не более одного раза за всё время своего существования в стеке, отложенных монет всегда достаточно. Суммарная стоимость $n$ операций push — не больше $2n$ условных единиц (две монеты на операцию), а стоимость всех операций pop и multipop полностью покрывается заранее отложенными монетами и не добавляет новых расходов сверху. Итого суммарная стоимость произвольной последовательности из $n$ операций — $O(n)$, а значит, амортизированная стоимость одной операции любого из трёх видов — $O(1)$, даже несмотря на то, что отдельная операция multipop в худшем случае стоит $O(n)$.
Почему это важно
Амортизированный анализ объясняет, почему интуитивно «дорогие» операции на практике оказываются дёшевы в потоковой обработке данных — а это ровно та ситуация, в которой ML-инженер постоянно работает: онлайн-обучение, накопление признаков батчами, буферизация потока событий для последующей пакетной обработки. Зная, что append в список или добавление ключа в словарь Python амортизированно константны, можно спокойно наращивать структуры данных элемент за элементом в цикле обработки потока, не беспокоясь о том, что суммарная стоимость окажется квадратичной. Но важно помнить границу этой гарантии: амортизированный анализ говорит о суммарной стоимости длинной последовательности операций, а не о стоимости одной конкретной операции — если система работает в реальном времени и не может позволить себе редкий, но заметный «всплеск» задержки при ресайзе внутреннего буфера (например, обработка сигналов с жёстким требованием по задержке отклика), одной амортизированной оценки недостаточно, и нужно смотреть на гарантии в худшем случае для отдельной операции.
Практика: 30 заданий
Базовые (задания 1–10)
Задание 1. Определи временную сложность фрагмента кода:
def print_all(arr):
for x in arr:
print(x)
Задание 2. Определи временную сложность доступа arr[42] к элементу массива Python по фиксированному индексу.
Задание 3. Для отсортированного массива из миллиарда элементов сравни число операций бинарного и линейного поиска в худшем случае.
Задание 4. Определи временную сложность:
def sum_pairs(arr):
total = 0
for i in range(len(arr)):
for j in range(len(arr)):
total += arr[i] * arr[j]
return total
Задание 5. Определи итоговую сложность функции, состоящей из двух последовательных, не вложенных друг в друга частей: сначала линейный проход по массиву ($O(n)$), затем двойной вложенный цикл ($O(n^2)$).
Задание 6. Во сколько раз вырастет время выполнения при увеличении $n$ в 10 раз для алгоритмов со сложностью $O(n)$, $O(n^2)$ и $O(\log n)$?
Задание 7. Докажи формально, что $5n + 20 = O(n)$: подбери подходящие константы $c$ и $n_0$.
Задание 8. Определи пространственную сложность функции:
def make_squares(arr):
result = []
for x in arr:
result.append(x ** 2)
return result
Задание 9. Сравни на конкретных числах ($n = 1000$) величины $n \log_2 n$ и $n^2$.
Задание 10. Определи временную и пространственную сложность рекурсивного вычисления факториала (см. пример из раздела о временной и пространственной сложности).
Средние (задания 11–20)
Задание 11. Определи сложность тройного вложенного цикла, перемножающего две квадратные матрицы $n \times n$ (см. пример matmul выше).
Задание 12. Определи сложность цикла:
i = 1
while i < n:
print(i)
i *= 2
Задание 13. Определи сложность вложенного цикла, где внутренний диапазон зависит от внешнего индекса:
for i in range(n):
for j in range(0, i):
print(i, j)
Задание 14. Реши рекуррентное соотношение $T(n) = 2T(n/2) + n$ (сортировка слиянием) через основную теорему о рекуррентных соотношениях.
Задание 15. Реши рекуррентное соотношение $T(n) = T(n - 1) + 1$ и определи, какому виду алгоритма оно соответствует.
Задание 16. Наивный поиск похожих объектов сравнивает каждый объект с каждым (все пары) среди $n$ объектов, каждый из которых описан $d$ признаками. Оцени временную сложность в терминах $n$ и $d$ и подставь конкретные числа: $n = 100\,000$, $d = 128$.
Задание 17. В динамический массив с удвоением ёмкости добавили $n = 1000$ элементов, начиная с пустого массива ёмкостью 1. Оцени суммарное число операций копирования при всех расширениях и убедись, что оно меньше $2n$.
Задание 18. Сравни ожидаемое время выполнения пузырьковой сортировки ($O(n^2)$) и сортировки слиянием ($O(n \log n)$) для массива из миллиона элементов, если условно считать скорость процессора $10^8$ операций в секунду.
Задание 19. Определи сложность фрагмента:
i = n
while i > 1:
for j in range(n):
print(j)
i //= 2
Задание 20. При поиске элемента среди $n = 10^9$ записей сравни, насколько практически значима разница между линейным поиском в неотсортированном массиве и бинарным поиском в отсортированном, если один поиск занимает единицы наносекунд на сравнение.
Продвинутые (задания 21–30)
Задание 21. Реши рекуррентное соотношение тернарного поиска (аналог бинарного поиска, но с делением диапазона на три части): $T(n) = T(n/3) + O(1)$.
Задание 22. Для наивного рекурсивного вычисления чисел Фибоначчи (пример fib_naive выше) запиши рекуррентное соотношение, определи класс сложности и сравни с версией, использующей мемоизацию (кэширование уже посчитанных значений).
Задание 23. k-NN классификатор без специальных структур поиска делает предсказание для одного объекта за $O(n \cdot d)$ (сравнение с каждым из $n$ объектов обучающей выборки по $d$ признакам). Оцени сложность получения предсказаний для $m$ новых объектов и объясни, почему это плохо масштабируется в продакшене с высоким трафиком запросов.
Задание 24. Вычисление всех попарных косинусных расстояний между $n = 1\,000\,000$ текстовыми эмбеддингами размерности $d = 768$ (типичный размер эмбеддинга современной языковой модели) выполняется наивным перебором пар. Оцени число операций и сделай вывод о применимости такого подхода.
Задание 25. Реши рекуррентное соотношение $T(n) = 4T(n/2) + n^2$ через основную теорему о рекуррентных соотношениях.
Задание 26. Дерево решений строится так: на каждом узле сортируются значения всех $d$ признаков по $n$ объектам, попавшим в узел ($O(n \log n \cdot d)$ работы на узел), а глубина дерева в среднем — $O(\log n)$. Оцени итоговую сложность построения всего дерева, если на каждом уровне суммарно обрабатывается $n$ объектов (распределённых по узлам этого уровня).
Задание 27. Хэш-таблица с динамическим ресайзом (аналогично динамическому массиву, но с пересчётом хэшей всех ключей при превышении порога заполненности) увеличивает внутренний массив вдвое при достижении коэффициента заполнения 0,75. Докажи амортизированную сложность вставки $O(1)$ по аналогии с динамическим массивом.
Задание 28. Рекурсивная сортировка слиянием на каждом уровне рекурсии создаёт временные списки для хранения половин массива, суммарно занимающие $O(n)$ памяти на уровень, а глубина рекурсии — $O(\log n)$. Оцени итоговую пространственную сложность алгоритма при реализации, которая не переиспользует память между уровнями.
Задание 29. Обучение линейной регрессии методом нормальных уравнений имеет сложность $O(nd^2 + d^3)$ (где $n$ — число объектов, $d$ — число признаков), а градиентный спуск — $O(nd)$ на одну итерацию, при $T$ итерациях до сходимости — $O(T \cdot nd)$. При каком соотношении $n$, $d$ и $T$ градиентный спуск становится предпочтительнее нормальных уравнений?
Задание 30. Пайплайн предобработки данных состоит из трёх последовательных этапов: сортировка $n$ записей по ключу ($O(n \log n)$), вычисление всех попарных расстояний между записями для детекции похожих дубликатов ($O(n^2)$) и унитарное кодирование категориальных признаков ($O(n \cdot k)$, где $k$ — число уникальных категорий). Определи итоговую сложность пайплайна и укажи, какой этап станет узким местом при росте $n$.
Частые ошибки
❌ Ошибка: Путать сложность в худшем случае с сложностью в среднем случае — например, утверждать, что быстрая сортировка (quicksort) всегда работает за $O(n \log n)$.
✅ Правильно: Указывать конкретно, о каком случае идёт речь: у quicksort средняя сложность — $O(n \log n)$, но в худшем случае (например, на уже отсортированном массиве при неудачном выборе опорного элемента) — $O(n^2)$.
💡 Почему: Разные реализации и разные входные данные приводят к разному поведению одного и того же алгоритма; смешение «типичного» и «гарантированного» поведения приводит к неверным ожиданиям по времени отклика в продакшене, особенно на редких, но не невозможных «плохих» входах.
❌ Ошибка: Игнорировать константы и считать, что алгоритм с лучшей асимптотикой всегда быстрее на практике при любом $n$.
✅ Правильно: Учитывать, что $O$-нотация описывает поведение только при достаточно больших $n$ (то самое $n_0$ из определения); при маленьких входных данных алгоритм с худшей асимптотикой, но меньшими константами (например, сортировка вставками для очень коротких массивов), может быть быстрее алгоритма с лучшей теоретической сложностью.
💡 Почему: Именно поэтому промышленные библиотеки сортировки используют гибридные алгоритмы (например, Timsort в Python или introsort в C++), которые переключаются на простую сортировку вставками для маленьких подмассивов внутри более сложной рекурсивной схемы — асимптотика важна на больших $n$, а на малых решают константы.
❌ Ошибка: Забывать учитывать пространственную сложность рекурсии, считая, что рекурсивная и итеративная версии алгоритма всегда эквивалентны.
✅ Правильно: Отдельно оценивать память стека вызовов при рекурсии — глубокая рекурсия может привести к переполнению стека даже при формально приемлемой временной сложности.
💡 Почему: Временная и пространственная сложность — независимые характеристики: алгоритмы могут совпадать по одной и заметно различаться по другой, как в примере с рекурсивным и итеративным факториалом.
❌ Ошибка: Складывать сложности вложенных циклов вместо их перемножения — например, считать, что двойной вложенный цикл по $n$ даёт $O(n) + O(n) = O(n)$.
✅ Правильно: Для вложенных (не последовательных, а именно вложенных друг в друга) циклов сложности перемножаются: $O(n) \cdot O(n) = O(n^2)$.
💡 Почему: Складывать нужно сложности последовательных, не вложенных блоков кода; перепутать эти два правила — самая частая техническая ошибка новичка при определении сложности по коду, и она приводит к заниженной на порядок оценке.
❌ Ошибка: Считать, что более низкая теоретическая сложность автоматически означает более быстрый код на практике, забывая о работе с памятью и векторизации.
✅ Правильно: Учитывать, что векторизованные операции numpy и pandas, формально имеющие ту же асимптотику $O(n)$, что и наивный цикл на чистом Python, на практике работают в десятки и сотни раз быстрее за счёт реализации на компилированном C, использования SIMD-инструкций процессора и эффективной работы с кэшем.
💡 Почему: $O$-нотация скрывает константы, а разница в константах между интерпретируемым циклом Python и векторизованной операцией numpy — это именно тот самый спрятанный множитель $c$ из формального определения, который может быть огромным.
❌ Ошибка: Утверждать, что каждая отдельная операция append в динамическом массиве гарантированно стоит $O(1)$, ссылаясь на амортизированную сложность.
✅ Правильно: Амортизированная оценка $O(1)$ гарантирует малую суммарную стоимость длинной последовательности операций, но не исключает, что отдельная конкретная операция (в момент ресайза) обойдётся заметно дороже — $O(n)$.
💡 Почему: Для систем с жёсткими требованиями к задержке отдельного запроса (системы реального времени) важна гарантия по худшему случаю для одной операции, а не только по суммарной стоимости серии операций — амортизированный анализ и анализ худшего случая для отдельной операции отвечают на разные вопросы.
Главное запомнить
✅ Временная сложность $T(n)$ и пространственная сложность $S(n)$ измеряют рост числа операций и объёма дополнительной памяти алгоритма в зависимости от размера входа $n$, а не секунды или мегабайты, зависящие от конкретного железа
✅ $f(n) = O(g(n))$ означает, что существуют константы $c > 0$ и $n_0$ такие, что $f(n) \leq c \cdot g(n)$ при всех $n \geq n_0$ — верхняя граница роста с точностью до постоянного множителя, обычно применяемая к худшему случаю
✅ Шесть базовых классов сложности по возрастанию роста: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$ — каждый следующий строго опережает предыдущий при $n \to \infty$
✅ Для последовательных блоков кода сложности складываются и остаётся только доминирующее слагаемое; для вложенных циклов сложности перемножаются
✅ Сложность рекурсивных алгоритмов описывается рекуррентным соотношением $T(n) = aT(n/b) + f(n)$ и решается через основную теорему о рекуррентных соотношениях или прямым раскрытием рекурсии
✅ Амортизированная сложность — усреднённая по длинной последовательности операций стоимость одной операции; она позволяет честно оценивать структуры данных вроде динамического массива, где редкие дорогие операции компенсируются множеством дешёвых
✅ Геометрический (а не линейный) рост ёмкости — необходимое условие амортизированной константной сложности вставки в динамический массив и в хэш-таблицу
✅ $O$-нотация отбрасывает константы и младшие слагаемые — она описывает поведение при больших $n$, а не точное время на конкретном входе; на маленьких $n$ константы могут решать больше, чем асимптотика
✅ Наивный перебор всех пар объектов — характерный источник квадратичной сложности в задачах поиска похожих объектов, и именно он не масштабируется на большие датасеты
✅ Понимание сложности алгоритма определяет, стоит ли вообще запускать его на реальных объёмах данных, или заранее нужно искать альтернативный подход с лучшей асимптотикой
Связь с другими темами курса
🔙 Откуда пришли: символы $O$ и $o$ Ландау для сравнения бесконечно малых, уже встречавшиеся в университетском блоке математического анализа при сравнении функций вблизи предельной точки — здесь та же идея применена к росту дискретных функций числа операций алгоритма при $n \to \infty$
🔜 Куда идём:
- Массивы и списки (урок 252) — первая конкретная пара структур данных, операции над которыми сравниваются именно через введённую здесь нотацию: доступ по индексу, вставка, удаление
- Стеки и очереди (урок 253) — специализированные структуры с гарантированной $O(1)$ сложностью базовых операций
- Дальше по курсу: хэш-таблицы, деревья, графы, алгоритмы сортировки и поиска — каждая новая структура и каждый новый алгоритм будут описываться в первую очередь через их временную и пространственную сложность, введённую в этом уроке
🎯 В машинном обучении: сложность алгоритмов определяет масштабируемость всего, что ты строишь — от предобработки данных (сортировки, группировки, вычисления попарных расстояний) до самого обучения моделей (нормальные уравнения линейной регрессии, построение деревьев решений, k-means, k-NN) и инференса в продакшене, где сложность одного предсказания напрямую превращается в задержку ответа сервиса для пользователя
Интересные факты
📌 Буква $O$ в нотации происходит не от английского слова, а от немецкого «Ordnung» — порядок; её ввёл Пауль Бахман в 1894 году в книге о теории чисел, за много десятилетий до появления первых электронных компьютеров.
📌 Дональд Кнут, систематизировавший использование асимптотической нотации в информатике, в статье 1976 года «Big Omicron and big Omega and big Theta» («О-большое, Омега-большое и Тета-большое») специально уточнил произношение символа $O$: он предложил читать его как английское «big oh» (буквально — «биг оу», заглавная буква «о»), а не как «big zero» («биг зиро», то есть «ноль»), хотя визуально символы неразличимы — путаница на этот счёт существует в сообществе программистов до сих пор.
📌 Классы сложности отдельных алгоритмов ($O(n)$, $O(n^2)$ и так далее), изучаемые в этом уроке, не стоит путать с классами сложности вычислительных задач в теории сложности вычислений — знаменитая нерешённая математическая проблема $P$ против $NP$ (одна из семи «задач тысячелетия» Института Клэя с призом в миллион долларов) касается второго понятия: существуют ли для задач, решение которых легко проверить, столь же эффективные алгоритмы, чтобы его найти.
📌 Быстрая сортировка (quicksort), несмотря на квадратичную сложность в худшем случае, на практике почти всегда обгоняет сортировку слиянием с гарантированной $O(n \log n)$-сложностью — из-за меньших констант и более эффективной работы с кэшем процессора; именно поэтому стандартные библиотеки сортировки в большинстве языков программирования используют гибридные схемы (introsort), которые переключаются на альтернативный алгоритм только при обнаружении признаков «плохого» для quicksort случая.
Лайфхаки и полезные трюки
💡 Чтобы быстро прикинуть сложность кода, посчитай число вложенных друг в друга циклов, зависящих от размера входа: один цикл — обычно $O(n)$, два вложенных — $O(n^2)$, три — $O(n^3)$; это не строгое правило (диапазоны циклов могут зависеть от индексов), но хорошая первая прикидка перед более детальным анализом.
💡 Проверяй теоретическую оценку сложности эмпирически: замерь время выполнения на нескольких значениях $n$ (например, $1000, 2000, 4000, 8000$ — каждый раз вдвое больше предыдущего) и посмотри на отношение времён. Если время растёт вдвое — это $O(n)$, если вчетверо — $O(n^2)$, если восьмикратно — $O(n^3)$; такая проверка занимает пару минут и часто выявляет случайно закравшуюся квадратичную сложность там, где ожидалась линейная.
💡 В пайплайнах обработки данных всегда заменяй Python-циклы с накоплением результата в изменяемую структуру (например, повторные вызовы pd.concat в цикле) на векторизованные операции numpy/pandas или на однократную сборку списка с последующим объединением — это не просто вопрос константы, а нередко способ избежать случайной квадратичной сложности вместо линейной.
💡 Перед запуском алгоритма на боевых данных прикинь порядок итогового числа операций по известной сложности и размеру $n$: если получаются десятки триллионов операций, останавливайся и меняй подход заранее, а не после часа бесполезного ожидания зависшего скрипта.
💡 При выборе структуры данных смотри не на удобство синтаксиса, а на сложность нужной тебе операции: поиск элемента в списке — $O(n)$, поиск в множестве или словаре (хэш-таблице) — $O(1)$ в среднем случае. Замена list на set там, где нужна лишь проверка принадлежности, — одна из самых дешёвых и эффективных оптимизаций в реальном коде.
💡 Если рекурсивный алгоритм заметно пересчитывает одни и те же подзадачи много раз (классический признак — экспоненциальная сложность там, где интуитивно ожидалась полиномиальная, как в наивных числах Фибоначчи), добавь мемоизацию — кэширование уже посчитанных результатов по аргументам функции; в Python это можно сделать буквально одной строкой через декоратор functools.lru_cache, превращая экспоненциальный алгоритм в линейный без переписывания логики.
Нотация O-большое — не абстрактная математическая игрушка, а рабочий инструмент, который отвечает на самый практический вопрос инженера: доживёт ли этот код до реальных объёмов данных или сломается на первой сотне тысяч строк. Ты теперь умеешь не только читать готовую оценку сложности в документации библиотеки, но и выводить её самостоятельно — по структуре циклов, по рекуррентному соотношению рекурсии, по амортизированному анализу структуры данных. Это ровно тот фундамент, на котором держится весь следующий блок курса: каждая структура данных, которую ты изучишь дальше — массивы, списки, стеки, очереди, хэш-таблицы, деревья, графы, — будет описываться в первую очередь через сложность своих операций, и теперь этот язык для тебя не набор загадочных символов, а понятный и выводимый результат. В следующем уроке ты применишь его на практике к первой конкретной паре структур данных — массивам и связанным спискам — и увидишь, как один и тот же выбор структуры превращает алгоритм из $O(n)$ в $O(1)$ или наоборот.
Понял тему? Закрепи в боте! 🚀
Попрактикуйся на задачах и получи персональные рекомендации от AI
💪 Начать тренировку