Big O нотация — это математическая запись, описывающая асимптотическое поведение алгоритма. Она показывает, как растёт время выполнения или потребление памяти алгоритма при увеличении размера входных данных. **Основные сложности:** - **O(1)** — константное время (доступ к элементу массива). - **O(log n)** — логарифмическое (бинарный поиск). - **O(n)** — линейное (поиск в неотсортированном массиве). - **O(n log n)** — линейно-логарифмическое (быстрая сортировка). - **O(n²)** — квадратичное (пузырьковая сортировка). - **O(2ⁿ)** — экспоненциальное (рекурсивное вычисление чисел Фибоначчи). **Пример:** ``` # O(n) — линейная сложность def linear_search(arr, target): for item in arr: if item == target: return True return False # O(n²) — квадратичная сложность def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] ```