Откуда берется обозначение O(n) и почему оно лучше, чем O(n²)?

Нотация 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):

# Простой цикл, проходящий один раз по всем элементам списка
def linear_search(arr, target):
  for item in arr:
    if item == target:
      return True
  return False

Пример алгоритма O(n²):

# Вложенные циклы для сравнения всех пар элементов списка
def bubble_sort(arr):
  n = len(arr)
  for i in range(n):
    for j in range(0, n - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]

При выборе алгоритма, предпочтение отдается тому, который имеет меньшую асимптотическую сложность для больших входных данных, поскольку это напрямую влияет на производительность и масштабируемость решения.