Ответ
Big O нотация — это математическая запись, используемая в информатике для описания асимптотического поведения алгоритма. Она позволяет оценить, как время выполнения или потребление памяти алгоритма масштабируется при увеличении размера входных данных.
Почему это важно? Понимание Big O помогает выбирать наиболее эффективные алгоритмы для конкретных задач, особенно при работе с большими объемами данных, и предсказывать их производительность.
Основные классы сложности:
- O(1) (Константная): Время выполнения не зависит от размера входных данных (например, доступ к элементу массива по индексу).
- O(log n) (Логарифмическая): Время выполнения растет медленно с увеличением данных (например, бинарный поиск в отсортированном массиве).
- O(n) (Линейная): Время выполнения прямо пропорционально размеру входных данных (например, поиск элемента в неотсортированном списке).
- O(n log n) (Линейно-логарифмическая): Эффективные алгоритмы сортировки (например, быстрая сортировка, сортировка слиянием).
- O(n²) (Квадратичная): Время выполнения растет как квадрат размера входных данных (например, пузырьковая сортировка, вложенные циклы).
- O(2ⁿ) (Экспоненциальная): Очень медленный рост, часто встречается в задачах полного перебора (например, рекурсивное вычисление чисел Фибоначчи без мемоизации).
Примеры на Python:
# 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]
return arr