Что такое Big O

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

Примеры:

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

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

# O(log n) — бинарный поиск
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

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