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