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

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

Основные варианты:

• 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

# O(1) — доступ по индексу
def get_first_element(arr):
    return arr[0] if arr else None

Big O помогает оценить эффективность алгоритма, игнорируя константы и низкоуровневые оптимизации.