Способ сравнить алгоритмы, не запуская их: как растёт время работы с ростом входа. Отбрасывает константы и оставляет то, что решает на больших данных.
- число объектов в выборке
- функция, о которой идёт речь
Ключевые тезисы
- O(·) — верхняя оценка роста; константы и младшие члены отбрасываются как несущественные на больших n.
- Разница между O(n log n) и O(n²) — это разница между минутой и неделей на миллионе элементов.
- молчит о константах: на малых входах простой O(n²) часто быстрее хитрого O(n log n).
Какую задачу решает
Два способа посчитать одно и то же дают разное время работы, и на маленьких данных разница незаметна. отвечает на вопрос, что будет, когда данных станет в сто раз больше: останется ли время приемлемым или задача перестанет решаться.
Приём в том, чтобы отбросить всё несущественное. Константы зависят от языка, процессора и настроения компилятора; младшие слагаемые перестают влиять, как только вход подрастёт. Остаётся один член — скорость роста, — и именно он решает, доживёт ли расчёт до утра.
Практическая ценность не в умении писать O-нотацию, а в умении посмотреть на цикл внутри цикла и сказать: на миллионе записей это не запустится. Такая оценка делается за секунды и экономит дни.
Есть список пользователей и список заказов, нужно к каждому заказу приписать пользователя. Наивное решение — для каждого заказа пробежать список пользователей: O(n·m). На тысяче пользователей и десяти тысячах заказов это десять миллионов операций — доли секунды, всё хорошо. Через год пользователей миллион, заказов десять миллионов, и то же самое становится 10¹³ операций — часы. Решение — положить пользователей в словарь по идентификатору: построение O(n), каждый поиск O(1), суммарно O(n + m). На новых данных это одиннадцать миллионов операций вместо десяти триллионов. Ни строчки хитрого кода, только смена структуры.
Подробный разбор
Запись читается так: начиная с некоторого размера входа, растёт не быстрее с точностью до постоянного множителя. Это утверждение о скорости роста, а не о времени: не значит «n операций», оно значит «пропорционально n».
| Сложность | n = 10³ | n = 10⁶ | n = 10⁹ |
|---|---|---|---|
| O(1) | мгновенно | мгновенно | мгновенно |
| O(log n) | 10 шагов | 20 шагов | 30 шагов |
| O(n) | мгновенно | миллисекунды | секунды |
| O(n log n) | мгновенно | секунда | минуты |
| O(n²) | миллисекунды | часы | невозможно |
| O(2ⁿ) | невозможно | невозможно | невозможно |
Граница между «работает» и «не работает» проходит примерно между O(n log n) и O(n²). Всё, что квадратично, на миллионе записей уже не считается. Это единственная строчка из таблицы, которую стоит помнить наизусть.
| Алгоритм | Лучший | Средний | Худший |
|---|---|---|---|
| O(n log n) | O(n log n) | O(n²) | |
| слиянием | O(n log n) | O(n log n) | O(n log n) |
| Поиск в хеш-таблице | O(1) | O(1) | O(n) |
| Поиск в дереве (сбалансированном) | O(1) | O(log n) | O(log n) |
Какую оценку брать, зависит от того, кто выбирает данные. Если вход приходит от пользователя, а система должна держать нагрузку, ориентируйтесь на худший случай: злоумышленник подберёт именно его. Если данные ваши и типичные — средний честнее.
с опорным элементом «первый в массиве» деградирует до квадратичной на уже отсортированных данных — то есть на самом частом входе в практике. Именно поэтому во всех приличных реализациях опорный выбирают случайно или берут медиану трёх.
Добавление в динамический массив обычно стоит константу: записали в свободную ячейку. Но когда место кончилось, массив выделяется заново вдвое больше и всё копируется — это . Значит ли это, что добавление стоит ?
Нет. Дорогая операция случается всё реже: после копирования следующее произойдёт только через добавлений. Суммарная стоимость добавлений — порядка , то есть в среднем константа на операцию. Это и называется амортизированной оценкой.
Удвоение здесь не случайно. Если увеличивать массив на фиксированное число ячеек, копирований станет штук, и суммарная стоимость вырастет до квадратичной. Геометрический рост — то, что делает амортизацию константной.
У алгоритма две стоимости, и вторая часто оказывается ограничивающей. слиянием требует дополнительной памяти, быстрая — на , пирамидальная — константу.
- In-place — алгоритм работает в исходном массиве, дополнительной памяти константа.
- Потоковый — данные читаются один раз и целиком в память не помещаются.
- Внешний — данные на диске, алгоритм минимизирует число обращений.
ускоряет , запоминая ответы, — плата ровно памятью. Ту же сделку заключают индексы в базе: чтение ускоряется, место и стоимость записи растут. Обратная сделка тоже бывает: пересчитать значение вместо хранения. В обучении глубоких сетей это стандартный приём — gradient checkpointing.
отбрасывает константы, а на реальном железе они бывают в сотни раз. Главный источник — иерархия памяти: обращение к кешу быстрее обращения к оперативной примерно в сто раз. Алгоритм, читающий память последовательно, выигрывает у алгоритма с той же асимптотикой, прыгающего по адресам.
- вставками обгоняет быструю на массивах короче 30–50 элементов — поэтому все реальные реализации гибридные.
- Проход по массиву быстрее прохода по связному списку той же длины, хотя обе операции линейны.
- Матричное умножение по Штрассену асимптотически быстрее, но выигрывает только на очень больших .
Практический вывод: решает, какой алгоритм брать, профайлер решает, что чинить в уже выбранном. Менять их местами — обычный источник бесполезной оптимизации.
Где применяется
- Выбор алгоритмаСравнить два решения, не написав ни одного из них.
- Оценка масштабируемостиПонять заранее, доживёт ли до десятикратного роста данных.
- Ревью кодаВложенный цикл по большой коллекции — повод остановиться и посчитать.
- СобеседованиеПервый вопрос после «я решил» — «за сколько это работает».
Плюсы, минусы и альтернативы
Плюсы
- Не зависит от машины, языка и компилятора — сравнение честное.
- Считается на бумаге за минуту, до написания кода.
- Предсказывает поведение при росте данных, который ещё не наступил.
Минусы
- Молчит о константах: O(n log n) с огромной константой проигрывает O(n²) на тысяче элементов.
- Не учитывает кеш процессора, а он даёт разницу в разы на одинаковой асимптотике.
- Худший случай бывает недостижим на реальных данных, и оценка по нему пессимистична.
Брать, если
- Всегда, когда данные могут вырасти.
- Перед выбором структуры данных под задачу.
Не брать, если
- Когда вход фиксирован и мал: там решают константы, и мерить надо профайлером.
- Для оптимизации уже работающего кода — сначала измерьте, где время уходит на самом деле.
Чем заменяют
Видеолекции
Записи университетских курсов, где эта тема звучит. Где у записи есть тайм-коды, ссылка открывает её с нужной секунды; где их не проставили — с начала.
Связанные темы
Алгоритмическое мышление
Problem Pattern Recognition85%
Как распознать паттерн задачи · Алгоритмы и структуры данныхУровень над алгоритмами: по формулировке условия понять, какой приём здесь работает. «Отсортированный массив», «подряд идущие элементы», «ближайший больший справа» — каждая такая фраза указывает на конкретное семейство решений.
Recursion and Divide and Conquer85%
Рекурсия и разделяй-и-властвуй · Алгоритмы и структуры данныхЗадача сводится к таким же задачам меньшего размера. Основа сортировки слиянием, быстрой сортировки, обхода деревьев и почти всей динамики.
Dynamic Programming85%
Динамическое программирование · Алгоритмы и структуры данныхПеребор, в котором каждое подсостояние считается ровно один раз. Превращает экспоненциальный перебор в полиномиальный, если подзадачи перекрываются.
Greedy Algorithms85%
Жадные алгоритмы · Алгоритмы и структуры данныхНа каждом шаге берём локально лучший вариант и не пересматриваем решение. Работает не всегда — но когда работает, проще и быстрее динамики.
Binary Search85%
Бинарный поиск · Алгоритмы и структуры данныхПоловинное деление на отсортированных данных: за логарифм шагов вместо линейного перебора. Приём шире поиска — им ищут ответ в любой монотонной задаче.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
O-нотация
Верхняя оценка роста с точностью до константы. Читается как «растёт не быстрее, чем».
Разбор ниже: Что означает O-нотацияХудший и средний случай
в среднем O(n log n), в худшем O(n²). Разница решает, можно ли ей доверять.
Разбор ниже: Худший, средний и лучший случайАмортизированная сложность
Средняя стоимость операции в длинной серии. Так добавление в динамический массив стоит O(1).
Разбор ниже: Амортизированная сложностьСложность по памяти
Сколько дополнительного места нужно алгоритму. Часто важнее времени.
Разбор ниже: ПамятьСкрытая константа
То, что отбрасывает. На малых входах она и определяет победителя.
Разбор ниже: Чего асимптотика не видитТема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.