Асимптотическая сложность — это способ понять, как будет меняться время работы программы, когда объём данных сильно вырастет. Обозначается нотацией Big O. Понятие часто встречается в программировании, поэтому его любят спрашивать на собеседованиях. Разберём кратко и наглядно 9 видов, начиная от самого быстрого, с примерами на Python.
Порядок роста сложности (от быстрого к медленному)
1. O(1) — константное время
Время выполнения не зависит от размера данных.
Пример: доступ к элементу массива по индексу.
В результате получим единицу. Обращение к элементу массива происходит сразу, то есть 1 раз. Список (в нашем случае m) — структура данных, в которой каждому индексу соответствует значение. Если мы знаем индекс, то мы будем знать и значение.
2. O(logn) — логарифмическое время
Время растёт очень медленно. Основание логарифма может быть любым, но, как правило, это двойка (результат логарифма после знака равно это то, в какую степень нужно возвести основание, чтобы получить n. Например, если основание 2, n = 8, то log2 8 = 3).
Пример: бинарный поиск в отсортированном массиве.
В цикле while продолжаем, пока не найдём нужный элемент или пока диапазон поиска не станет пустым. При каждой итерации делим текущий диапазон пополам и сужаем границы поиска — так размер области, где может находиться элемент, сокращается в два раза. Это и есть сложность алгоритма — log2 10 = 3 раза мы поделим массив (с округлением).
3. O(n) — линейное время
Время пропорционально размеру данных: удвоение данных → удвоение времени.
Пример: проход по всем элементам массива.
Проходим по всем элементам списка, чтобы найти сумму. К каждому элементу обращаемся 1 раз, соответственно ко всем элементам нужно обратиться n раз.
4. O(nlogn) — линейно‑логарифмическое время
Растёт чуть быстрее линейного, но остаётся практичным для больших данных.
Пример: эффективные алгоритмы сортировки — Merge Sort, Quick Sort (в среднем). Если кратко, то это комбинация из перебора по n (то есть запускаем цикл for), затем делим, например, массив внутри этого перебора пополам (как в случае 2 с while), поэтому эти сложности перемножаются и получается O(nlogn).
5. O(n2) — квадратичное время (n в квадрате)
Время растёт пропорционально квадрату размера данных: удвоение данных → учетверение времени.
Пример: вложенные циклы (сортировка пузырьком, выборкой, вычисление попарных расстояний).
Чтобы перемножить каждый элемент на каждый, используем двойной цикл for.
6. O(n3) — кубическое время (n в степени 3)
Ещё медленнее: утроение данных → увеличение времени в 27 раз.
Пример: перемножение трёх матриц, тройные вложенные циклы. Аналогично для примера из пункта 5, но в цикле for j in range(len(n)) появляется еще цикл for k in range(len(n)).
7. O(nk) — полиномиальное время (общий случай, k≥1, n в степени k)
Обобщает O(n2), O(n3) и т. д. Чем больше k, тем медленнее.
k — это степень, целое число ≥ 1, которое показывает, в какой степени размер входных данных n влияет на число операций.
- При k=1: O(n1)=O(n) — линейное время.
- При k=2: O(n2) — квадратичное время.
- При k=3: O(n3) — кубическое время.
- И так далее.
Чем больше k, тем быстрее растёт число операций при увеличении n. В нашем разборе 5 и 6 виды являются частными случаями полиномиального времени. Количество циклов в простых случаях может быть равно k.
8. O(2n) — экспоненциальное время (2 в степени n).
Время удваивается с каждым новым элементом данных. Быстро становится неприемлемым.
Пример: перебор всех подмножеств множества, некоторые задачи коммивояжёра.
На каждой итерации внешнего цикла for количество строк в result удваивается, за счет чего увеличивается объём данных, который нужно обработать. После n итераций получим 2 в степени n строк.
9. O(n!) — факториальное время
Самый медленный класс: время растёт как факториал размера данных. Уже при n=20 число операций — десятки квинтиллионов (Например, факториал из 5 равен 5! = 5*4*3*2*1 = 120)
Пример: полный перебор перестановок.
Создаем различные перестановки из 1, 2, 3 с помощью рекурсии.
Знание асимптотическая сложности помогает прогнозировать, как изменится время работы при росте объёма данных, и выбирать эффективные алгоритмы.