Нотация O(n) (или Big O notation) описывает асимптотическое поведение функции, характеризующей время или память, используемые алгоритмом, по мере увеличения размера входных данных (n).
Математически, f(n) = O(g(n)) означает, что существуют положительные константы c и n₀ такие, что для всех n ≥ n₀, f(n) ≤ c * g(n). g(n) здесь представляет доминирующий член в выражении для f(n), отбрасывая константы и младшие члены.
Например, алгоритм, выполняющий 3n + 5 операций, будет иметь сложность O(n), так как при больших n член 3n доминирует, а константа 5 становится незначительной. Мы отбрасываем константу 3 и 5, оставляя член n.
Сложность O(n) означает, что время выполнения (или используемая память) растет линейно с увеличением размера входных данных. Если входные данные удваиваются, время выполнения примерно удваивается.
Сложность O(n²) означает, что время выполнения растет квадратично с увеличением размера входных данных. Если входные данные удваиваются, время выполнения увеличивается примерно в четыре раза.
O(n) лучше, чем O(n²), потому что при росте n функция n растет значительно медленнее, чем функция n². Это означает, что алгоритмы с линейной сложностью масштабируются гораздо лучше, чем алгоритмы с квадратичной сложностью, на больших объемах данных.
Рассмотрим пример:
| n | O(n) = n | O(n²) = n² |
|---|---|---|
| 1 | 1 | 1 |
| 10 | 10 | 100 |
| 100 | 100 | 10000 |
| 1000 | 1000 | 1000000 |
Как видно из таблицы, разница в производительности между O(n) и O(n²) становится заметной по мере увеличения n, и эта разница быстро растет.
Пример алгоритма O(n):
pythonПример алгоритма O(n²):
pythonПри выборе алгоритма, предпочтение отдается тому, который имеет меньшую асимптотическую сложность для больших входных данных, поскольку это напрямую влияет на производительность и масштабируемость решения.