Объяснение временной и пространственной сложности алгоритма.
Представьте две программы, выполняющие одну и ту же задачу. Если каждой из них передать тысячу записей, отличить их друг от друга будет невозможно. Но если передать миллиард, одна завершит работу ещё до того, как вы отпустите клавишу Enter, а другая будет продолжать работать ещё до следующего вторника.
Тот же ноутбук. Те же данные. Разница лишь во временной сложности, которая просто обозначает, насколько быстро возрастает рабочая нагрузка алгоритма по мере увеличения объема входных данных.
Мы разберем, что на самом деле означает этот термин, как он записывается в нотации Big O, как его вычислить на примере реального кода и где здесь вступает в игру пространственная сложность. А затем, в конце, мы перейдем к тому месту, где все это перестает быть домашним заданием и начинает стоить реальных денег: смарт-контракты.
Что такое временная сложность алгоритма?
Забудьте на мгновение о секундах. Временная сложность измеряется количеством шагов. Сравнения, присваивания, немного арифметических операций тут и там, и вы записываете итог как функцию от n, то есть размера входных данных.
Вот, пожалуй, самая скучная функция, которую только можно себе представить:
python def print_all(items): for item in items: print(item)
Десять предметов? Десять кругов по петле. Десять тысяч? Десять тысяч кругов.
Работа выполняется по прямой линии параллельно входным данным, поэтому мы называем её сложностью O(n).
Возможно, каждая поездка на самом деле обходится в три небольшие операции вместо одной. Хорошо, это 3n. Честно говоря, никому нет дела, потому что удвоение списка все равно удваивает работу, а именно такая кривая роста нам и нужна. Точное число специально опускается.
Именно поэтому на каждом курсе по структурам и алгоритмам и на половине собеседований по программированию уделяется особое внимание временной сложности. Если вы можете определить сложность алгоритма, просто взглянув на него, вы можете предположить, как он будет вести себя на входных данных, которые вы так и не успели протестировать. А в производственной среде это большая часть данных.
Почему время выполнения — плохой показатель эффективности алгоритма
Так почему бы просто не запустить программу с таймером? Многие так делают, и я их понимаю. Подвох в том, что время выполнения затягивает кучу всего, к чему ваш алгоритм не имеет никакого отношения:
- Оборудование. Мой пятилетний ноутбук и совершенно новый облачный бокс покажут совершенно разные результаты для одного и того же сценария.
- Язык программирования. Напишите один и тот же цикл на C и на Python, и вы можете увидеть разницу в 10 раз или даже больше.
- Системная нагрузка. Запускается какой-то фоновый процесс обновления, просыпается сборщик мусора, кэш холодный. Ваш результат меняется.
- Какими бы входными данными вы ни воспользовались. Сортировка, которая легко справляется с почти отсортированными данными, может медленно обрабатывать перемешанные данные.
Секундомер показывает результат одного измерения на одном устройстве с одним входным параметром. Запросите у него примерно в 100 раз больше данных, и он ничего не выдаст.
Количество шагов не меняется. Один и тот же алгоритм, одни и те же входные данные, и вы получаете одинаковое количество шагов, будь то Rust на стоечном сервере или JavaScript на чьем-то телефоне. Вот почему временная сложность — это честный вопрос для сравнения двух решений до проведения бенчмаркинга. Я бы все равно провел бенчмаркинг после этого, если это имеет значение. Это просто другой вопрос.
Пояснение к нотации О и другим асимптотическим обозначениям.
В учебниках это называется асимптотической записью, что звучит хуже, чем есть на самом деле. Вы позволяете n стать огромным и перестаёте обращать внимание на мелочи, поэтому постоянные множители и крошечные входные данные исчезают, и остаётся только кривая роста. Есть три таких примера, которые стоит знать:
| Обозначение | Что это описывает | Простой смысл | Пример |
|---|---|---|---|
| Большое О, О(f(n)) | Верхняя граница | Алгоритм развивается не быстрее, чем f(n). | Линейный поиск имеет сложность O(n). |
| Большая Омега, Ω(f(n)) | Нижняя граница | Для работы алгоритма требуется как минимум f(n) вычислительных ресурсов. | Любая сортировка с помощью сравнений представляет собой Ω(n log n) |
| Биг-Тета, Θ(f(n)) | Плотный переплет | Верхняя и нижняя границы совпадают. | Сортировка слиянием — это Θ(n log n) |
На практике вы будете слышать обозначение O примерно в 95% случаев. Оно устанавливает верхнюю границу, то есть время выполнения не будет расти быстрее, чем скорость внутри скобок. На моей первой проверке кода на реальной работе старший разработчик написал «O(n²), пожалуйста, исправьте» рядом с вложенным циклом, и это означало, что в худшем случае временная сложность будет квадратичной, и список скоро значительно увеличится.
Омега и Тета в основном изучаются на университетских курсах по анализу алгоритмов, и я, кажется, уже много лет не набирал ни одну из них на работе. Большая О выигрывает, потому что отвечает на то, что люди действительно спрашивают на совещаниях: «Насколько всё ухудшится, если трафик утроится?»
Есть один технический нюанс, который меня некоторое время смущал. Поскольку O — это всего лишь верхний предел, функция O(n) также является функцией O(n²), строго говоря, точно так же, как человек ростом 152 см — это «меньше 213 см». Верно, но бесполезно. Каждый приводит самую точную оценку, которую может обосновать, и я сделаю то же самое.
Классы с общей временной сложностью и примерами.
В реальном коде вы встретите не так уж много классов, может быть, семь, если считать самые сложные. Вот примерно сколько стоит каждый из них при n = 1000:
| Сорт | Имя | Типичный пример | Операции при n = 1000 |
|---|---|---|---|
| О(1) | Постоянный | Индекс массива, поиск в хеш-таблице | 1 |
| O(log n) | логарифмический | Бинарный поиск | ~10 |
| На) | Линейный | Сканирование списка | 1000 |
| O(n log n) | Линейно-арифметический | Сортировка слиянием, быстрая сортировка (среднее значение) | ~10 000 |
| O(n²) | Квадратичный | Вложенные циклы, сортировка пузырьком | 1 000 000 |
| O(2ⁿ) | Экспоненциальный | Наивная рекурсивная Фибоначчи | Во Вселенной существует больше, чем просто атомы. |
| На!) | Факториал | Коммивояжер, применяющий грубую силу | Ещё больше |
O(1): Постоянное время
Независимо от того, содержит ли ваш словарь Python десять ключей или десять миллионов, извлечение по одному ключу обходится примерно одинаково, как и чтение элементов[5] из списка. Эта плоскость и есть суть постоянного времени.
O(log n): логарифмическое время
Я рассматриваю их как алгоритмы типа «угадай число от 1 до 100», где каждая попытка исключает половину оставшихся вариантов. Бинарный поиск делает именно это на отсортированном списке:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
При сортировке миллиарда элементов требуется около 30 сравнений, в то время как обработка каждого элемента по отдельности может занять весь миллиард, и меня это до сих пор забавляет.
O(n) и O(n log n)
Линейный алгоритм посещает каждый элемент фиксированное количество раз, подобно тому, как вы бы искали наибольшее число в столбце электронной таблицы вручную. Сложность O(n log n) характерна для хорошей сортировки. Сортировка слиянием разбивает список на отдельные элементы (log n уровней разделения), а затем выполняет один линейный проход на каждый уровень при слиянии, поэтому время ее выполнения остается неизменным независимо от того, поступают ли данные отсортированными или перемешанными.
O(n²) и хуже
В коде, описывающем квадратичные функции, цикл почти всегда вложен в другой цикл, как, например, в этой проверке на дубликаты, которая сравнивает каждую пару:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
Экспоненциальный и факториальный рост намного хуже. Классическая рекурсивная функция Фибоначчи постоянно решает одни и те же подзадачи, поэтому каждое увеличение n на +1 примерно удваивает объем работы. При n = 20 вы этого не заметите; при n = 60 вы можете приготовить ужин, поесть, помыть посуду, и работа все равно не будет закончена.
Как пошагово рассчитать временную сложность
Для вычисления временной сложности практически никогда не требуется формальное доказательство. Я мысленно прокручиваю этот список, и он охватывает большую часть кода, который я вижу:
- Определите n. Выясните, что является размером входных данных: длина списка, количество узлов в графе, количество цифр в числе.
- Подсчитайте количество операций в каждой строке. Простые операторы (присваивания, сравнения, арифметические операции) стоят O(1).
- Сложите последовательные блоки. Два цикла, один за другим, каждый по n, дают n + n = 2n.
- Умножьте вложенные блоки. Цикл по n внутри другого цикла по n дает n × n = n².
- Опустите константы. 2n становится n, а 500 становится 1.
- Оставьте только доминирующий член. В n² + n часть n² затмевает остальную часть по мере роста n.
Быстро разобрались. Получается T(n) = 3n² + 5n + 2. Подставим миллион: 3n² = три триллиона, 5n = пять миллионов. Ошибка округления. Назовем это O(n²), готово.
Циклы, которые вместо пошагового выполнения повторяются, более хитры:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Каждый проход уменьшает n вдвое, поэтому этот цикл while завершается примерно после log₂(n) раундов. Это, по сути, и есть ответ на вопрос: «Когда временная сложность становится O(log n)?» Если оставшаяся часть уменьшается на постоянный множитель на каждом шаге, значит, вы достигли цели.
Рекурсии нужен ещё один инструмент — рекуррентное соотношение. Сортировка слиянием выполняет две задачи половинного размера, а затем слияние, поэтому T(n) = 2T(n/2) + n. Основная теорема — это шпаргалка для рекуррентных соотношений такой формы, и для этого случая она выдаёт O(n log n).
И вот эмпирическое правило из соревновательного программирования, на которое я часто опираюсь: обычная машина выполняет примерно 10⁸ простых операций в секунду. Очень приблизительно, но этого достаточно, чтобы проверить временную сложность решения, прежде чем нажать кнопку «Отправить». При n = 10⁵, O(n²) составляет около 10¹⁰ операций, поэтому происходит превышение времени выполнения. O(n log n) — это менее 2 миллионов. Всё проходит гладко.
Анализ наихудшего, наилучшего и среднего сценариев
Если подавать на вход один и тот же алгоритм разные значения, объем работы может резко меняться. Линейный поиск это хорошо демонстрирует:
- В идеальном случае, то, что вам нужно, окажется прямо на видном месте. Одно сравнение — и вы в проигрыше.
- В худшем случае: оно находится в самом конце или его там вообще нет. Это не сравнение.
- Средний случай: если вероятность того, что это произойдет где угодно, одинакова, вы проверите в среднем около n/2. Тем не менее, сложность по-прежнему O(n).
Спросите разработчика о «сложности» чего-либо, и он почти всегда назовет вам временную сложность в худшем случае, потому что это число — обещание, на которое можно опереться при планировании.
Допустим, ваш API обрабатывает запрос в худшем случае за O(n). Отлично, теперь вы знаете, как ведет себя самый медленный запрос, и вы также защищены, если кто-то намеренно отправляет вам некорректные данные. Люди действительно так делают: если злоумышленник выяснит, какие ключи приводят к коллизии вашей хеш-таблицы, то в течение некоторого времени вы будете видеть только эти ключи.
Стоит рассмотреть средний случай, когда неблагоприятный сценарий практически никогда не встречается. Быстрый сортировщик — яркий тому пример: в среднем он имеет сложность O(n log n), но снижается до O(n²), если наивно выбирать опорные элементы на уже отсортированных данных. Стандартные библиотеки обходят эту проблему, используя случайные опорные элементы или переключаясь на другой алгоритм сортировки, когда рекурсия становится подозрительно глубокой.
Что такое пространственная сложность и вспомогательное пространство?
Память — это ещё один фактор, влияющий на производительность алгоритма. Пространственная сложность отслеживает, сколько памяти требуется по мере увеличения размера входных данных, и её обозначают той же нотацией O, что и время.
Часть этой памяти — это сами входные данные, за которые вы платите независимо от того, что с ними делаете. Часть, которую вы фактически контролируете, называется вспомогательным пространством, то есть дополнительными данными, которые ваш код выделяет во время работы, такими как временные переменные и новые массивы, а также стеком вызовов, о котором никто не помнит, пока он не даст о себе знать.
Несколько простых примеров:
- Для обмена двумя переменными требуется пара слотов независимо от всего остального, поэтому это вспомогательное пространство O(1).
- Копирование списка из n элементов в новый список требует дополнительных затрат памяти в размере O(n).
- Рекурсивный обход на n уровнях оставляет n кадров в стеке, что занимает пространство O(n), даже если вы никогда не создавали массив.
Я наблюдал, как начинающий разработчик потратил целый день на решение последней проблемы. Его рекурсивная функция выглядела так, будто вообще не использует память, но каждый незавершенный вызов оставался в стеке в ожидании возврата из более глубоких стеков, и при большом входном значении вся система завершалась с переполнением стека.
Многие методы оптимизации сводятся к обмену памяти на время или наоборот. Мемоизация кэширует уже вычисленные результаты, что сокращает время вычислений Фибоначчи с O(2ⁿ) до O(n) в обмен на память O(n). Хеш-таблицы позволяют получить среднее время поиска O(1) за счет использования памяти в корзинах. На сервере с 64 ГБ оперативной памяти такой обмен обычно очевиден, но на микроконтроллере или внутри смарт-контракта об этом стоит задуматься.
Временная и пространственная сложность распространенных структур данных
Выбор правильной структуры данных обычно лучше, чем микронастройка всего, что находится внутри цикла. Средняя стоимость для тех структур, которые вы будете использовать чаще всего:
| Структура данных | Доступ | Поиск | Вставлять | Удалить | Космос |
|---|---|---|---|---|---|
| Множество | О(1) | На) | На) | На) | На) |
| Связанный список | На) | На) | О(1) | О(1) | На) |
| Хеш-таблица | н/д | О(1) | О(1) | О(1) | На) |
| Сбалансированное бинарное дерево поиска | O(log n) | O(log n) | O(log n) | O(log n) | На) |
| Бинарная куча | O(1) для мин/макс | На) | O(log n) | O(log n) | На) |
Два примечания. Вставка и удаление в связанном списке занимают O(1) времени только в том случае, если узел уже находится в вашем распоряжении. А хеш-таблица может стать O(n), если много ключей конфликтуют.
Алгоритмы сортировки также сильно различаются:
| Алгоритм сортировки | Лучший | Средний | Худший | Вспомогательное пространство |
|---|---|---|---|---|
| Сортировка пузырьком | На) | O(n²) | O(n²) | О(1) |
| Сортировка слиянием | O(n log n) | O(n log n) | O(n log n) | На) |
| Быстрая сортировка | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Сортировка кучей | O(n log n) | O(n log n) | O(n log n) | О(1) |
Сортировка слиянием предсказуема, но требует дополнительной памяти. Сортировка кучей сортирует на месте и сохраняет тот же наихудший сценарий. Быстрая сортировка, несмотря на менее впечатляющий потолок, как правило, выигрывает на практике.
Временная сложность в блокчейне и смарт-контрактах
Вот тут-то и начинается самое интересное. На вашем собственном сервере некачественный алгоритм тратит ресурсы процессора и, возможно, раздражает пользователя. На Ethereum или любой другой блокчейне EVM он приводит к нерациональному расходованию средств. Каждая операция, выполняемая смарт-контрактом, стоит газа, оплачиваемого в собственной криптовалюте блокчейна, поэтому количество операций отображается в виде строки в чьем-то счете. Другими словами, высокая временная сложность имеет свою цену.
Допустим, у вас есть контракт, который перебирает всех держателей токенов для выплаты вознаграждений. Сложность O(n), и плата за газ увеличивается с каждым новым держателем. В день запуска никто этого не замечает.
Затем список держателей продолжает расти. В один прекрасный день для выплаты требуется больше газа, чем лимит газа блока, то есть максимальное количество газа, которое может поместиться в одном блоке. После этого транзакция не может быть завершена. Не «медленно». Она просто никогда не завершается, и средства, ожидавшие завершения этой функции, по сути, застревают. Аудиторы классифицируют подобные неограниченные циклы как атаки типа «отказ в обслуживании», и это вполне справедливо.
Решение заключается в простом и понятном мышлении в контексте сложных систем:
- Разделите работу на пакеты фиксированного размера, распределенные на несколько транзакций.
- Переверните всё так, чтобы каждый пользователь получал свою собственную награду. Каждый вызов занимает O(1).
- Замените петлю на доказательство Меркла.
Мне очень нравятся доказательства Меркла как пример того, почему log n так важен в блокчейне. Дерево Меркла хеширует большой объем данных в один корневой хеш.
Чтобы доказать, что одна запись принадлежит множеству из n элементов, вам потребуется примерно log₂(n) хешей. Для миллиона записей это примерно 20. Не миллион. Аирдропы опираются на это, а облегченные биткоин-кошельки используют тот же прием для подтверждения транзакции без загрузки всего блока.
Вне блокчейна — та же история. Представьте себе платежный бэкэнд, который сопоставляет каждую входящую транзакцию в блокчейне со счетом-фактурой, сканируя все открытые счета. Сложность O(n) на платеж, и скорость снижается по мере роста магазина. Поместите счета-фактуры в хеш-карту, где ключами являются адрес или ID, и каждое совпадение будет иметь сложность O(1). А если вы не хотите создавать и контролировать эту инфраструктуру самостоятельно, то криптовалютный платежный шлюз, такой как Plisio, сделает это за вас.
