Для чего используется нотация 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 игнорирует константы и меньшие члены, фокусируясь на доминирующем факторе роста.