ИнтВизАлгоритмы · модуль 12 из 14
Асимптотика: почему алгоритм важнее железа
Сколько операций выполнит алгоритм на n элементах и сколько это займёт на процессоре с 10⁹ операций в секунду. Сдвиньте n и посмотрите, какие алгоритмы перестают быть пригодными.
Ось операций логарифмическая: каждое деление в 10 раз больше предыдущего.
| Класс | Пример | Операций | Время при 10⁹ оп/с |
|---|
Число сравнений в сортировках (посчитано на сервере)
| Сортировка | n = 100 | n = 1 000 | n = 2 000 | n = 10 000 |
|---|
Теория
Сложность алгоритма описывает, как растёт число операций при росте размера входных данных $n$. Запись $f(n) = O(g(n))$ означает, что начиная с некоторого $n$ функция $f$ растёт не быстрее, чем $g$, с точностью до постоянного множителя:
$$ f(n) = O(g(n)) \iff \exists\, C > 0,\ n_0:\ f(n) \le C \cdot g(n) \ \text{для всех}\ n \ge n_0. $$
Основные классы роста, от медленного к быстрому:
| Класс | Пример | При $n = 10^6$ |
|---|---|---|
| $O(1)$ | поиск ключа в словаре | 1 операция |
| $O(\log n)$ | бинарный поиск | около 20 операций |
| $O(n)$ | линейный поиск | $10^6$ операций |
| $O(n \log n)$ | сортировка слиянием | около $2 \cdot 10^7$ операций |
| $O(n^2)$ | сортировка пузырьком | $10^{12}$ операций |
| $O(2^n)$ | перебор подмножеств | больше $10^{300\,000}$ операций |
Время работы оценивается как $T(n) \approx f(n) / 10^9$ секунд для процессора, выполняющего около $10^9$ простых операций в секунду. Постоянные множители и младшие слагаемые в O-нотации отбрасываются: $3n^2 + 100n$ и $n^2/2$ относятся к одному классу $O(n^2)$.
На логарифмической шкале степенные функции превращаются в прямые с наклоном, равным показателю степени, а экспонента $2^n$ растёт быстрее любой степени.
Где это применяется в IT
Сложность оценивают раньше, чем замеряют время: на код-ревью и на собеседованиях. Новый процессор ускорит программу в 2 раза, а замена алгоритма $O(n^2)$ на $O(n \log n)$ при $n = 10^6$ даёт ускорение примерно в 50 000 раз.
- Словари и множества. Поиск по ключу в
dictиsetвыполняется в среднем за $O(1)$. - Сортировка.
list.sort()иsorted()в Python используют Timsort со сложностью $O(n \log n)$. - Полный перебор. Алгоритмы $O(2^n)$ применимы только при $n$ до 30–40; дальше нужны эвристики или динамическое программирование.
Код на Python
Загружаю пример…