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)).