Классы сложности алгоритмов
Класс сложности алгоритма — это группа алгоритмов, у которых время работы или объём используемой памяти растут примерно одинаково при увеличении размера входных данных. Классы позволяют сравнивать алгоритмы независимо от конкретного компьютера и деталей реализации.
Размер входа обозначают буквой \(n\): это может быть длина строки, количество элементов массива, число вершин графа или другой параметр задачи. При оценке интересуются поведением алгоритма при больших \(n\) и обычно не учитывают постоянные множители и менее быстро растущие слагаемые.
Основные классы
| Класс | Пример роста | Смысл |
|---|---|---|
| \(O(1)\) | 1 | время почти не зависит от \(n\) |
| \(O(\log n)\) | \(\log_2 n\) | на каждом шаге размер задачи резко уменьшается |
| \(O(n)\) | \(n\) | один проход по входу |
| \(O(n\log n)\) | \(n\log n\) | часто встречается при эффективной сортировке |
| \(O(n^2)\) | \(n^2\) | перебор всех пар или два вложенных прохода |
| \(O(2^n)\) | \(2^n\) | перебор подмножеств |
| \(O(n!)\) | \(n!\) | перебор всех перестановок |
Например, алгоритм с двумя последовательными циклами по \(n\) элементов выполняется за \(O(n+n)=O(n)\). А два вложенных цикла обычно дают \(O(n\cdot n)=O(n^2)\). Сложность алгоритма может оцениваться отдельно для времени и для памяти.
В алгоритме один цикл выполняется \(n\) раз, а внутри него второй цикл — тоже \(n\) раз. Общее число повторений равно \(n\cdot n=n^2\), поэтому временная сложность имеет класс \(O(n^2)\). Если заменить внутренний цикл на постоянное действие, получится \(O(n)\).
\(O(n^2)\) не означает, что программа всегда выполняется ровно \(n^2\) операций. Это оценка порядка роста: например, \(3n^2+5n+7\) и \(n^2\) относятся к одному классу \(O(n^2)\). Кроме того, алгоритм класса \(O(n)\) на практике может быть медленнее алгоритма \(O(n^2)\) на очень маленьких входах.
Какой класс сложности имеет алгоритм, который перебирает все пары элементов массива из \(n\) элементов?
Главное
- Класс сложности описывает порядок роста времени или памяти при увеличении размера входа \(n\).
- В записи \(O(...)\) отбрасывают постоянные множители и менее быстро растущие слагаемые.
- Для больших входов обычно выгоднее алгоритм класса \(O(n)\), чем \(O(n^2)\), а полиномиальные классы обычно предпочтительнее экспоненциальных и факториальных.