Что такое нотация Big O в алгоритме

Big O — это математическая нотация, описывающая асимптотическую сложность алгоритма. Она показывает, как растёт время выполнения или потребление памяти при увеличении размера входных данных (n).

Основные виды сложности:

• O(1) – константная (доступ к элементу массива).
• O(log n) – логарифмическая (бинарный поиск).
• O(n) – линейная (поиск в неотсортированном массиве).
• O(n log n) – линейно-логарифмическая (быстрая сортировка).
• O(n²) – квадратичная (пузырьковая сортировка).

Пример:

# O(n) – линейный поиск
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

Big O оценивает худший случай, игнорируя константы и меньшие члены (O(2n + 3) → O(n)).