Откуда берется понятие временной сложности O(n) и почему она предпочтительнее O(n²)?

O(n) означает, что время выполнения алгоритма растет линейно с увеличением размера входных данных (n). Это происходит, когда алгоритм обрабатывает каждый элемент входных данных один раз или постоянное количество раз.

O(n²) означает, что время выполнения алгоритма растет квадратично с увеличением размера входных данных. Это типично для алгоритмов, где выполняются вложенные итерации по данным (например, два вложенных цикла, каждый из которых проходит по n элементам).

O(n) предпочтительнее O(n²) потому, что при увеличении размера входных данных (n) время выполнения алгоритма с временной сложностью O(n¹) растет значительно медленнее, чем у алгоритма с O(n²). Для больших n разница во времени выполнения становится очень существенной.

Пример: Если n = 1000: O(n) - время выполнения пропорционально 1000 O(n²) - время выполнения пропорционально 1000² = 1 000 000

# Пример алгоритма с O(n)
def find_max(arr):
  """Находит максимальный элемент в списке."""
  max_val = arr[0] # O(1) - константное время
  for item in arr: # O(n) - цикл по всем n элементам
    if item > max_val: # O(1)
      max_val = item # O(1)
  return max_val # O(1)
# Общая сложность: O(1) + O(n) * (O(1) + O(1)) + O(1) = O(n)

# Пример алгоритма с O(n²)
def bubble_sort(arr):
  """Сортировка пузырьком."""
  n = len(arr) # O(1)
  for i in range(n): # Внешний цикл - O(n)
    for j in range(0, n - i - 1): # Внутренний цикл - O(n)
      if arr[j] > arr[j + 1]: # O(1)
        arr[j], arr[j + 1] = arr[j + 1], arr[j] # O(1)
# Общая сложность: O(1) + O(n) * O(n) * (O(1) + O(1)) = O(n²)