Временная сложность (Big O) показывает, как растёт время выполнения алгоритма с увеличением размера входных данных. Основные варианты: - **O(1)** – константное время (доступ к элементу массива) ``` arr[0] # O(1) ``` - **O(log n)** – логарифмическое (бинарный поиск) ``` def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 ``` - **O(n)** – линейное (поиск в неотсортированном массиве) ``` for x in arr: # O(n) print(x) ``` - **O(n log n)** – (быстрая сортировка, сортировка слиянием) ``` sorted(arr) # Timsort: O(n log n) ``` - **O(n²)** – квадратичное (пузырьковая сортировка) ``` for i in range(n): # O(n²) for j in range(n): print(i, j) ``` - **O(2ⁿ)** – экспоненциальное (рекурсивный Фибоначчи без мемоизации) ``` def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # O(2ⁿ) ``` Также есть пространственная сложность – потребление памяти. В реальных задачах важно учитывать оба типа сложности.