Вот основные сложности алгоритмов в порядке возрастания: - **O(1)** - константная (доступ по индексу в массиве) ``` value = my_list[0] # O(1) ``` - **O(log n)** - логарифмическая (бинарный поиск) ``` def binary_search(arr, x): low, high = 0, len(arr)-1 while low <= high: mid = (low + high) // 2 if arr[mid] < x: low = mid + 1 elif arr[mid] > x: high = mid - 1 else: return mid return -1 ``` - **O(n)** - линейная (поиск в неотсортированном массиве) ``` for item in my_list: # O(n) print(item) ``` - **O(n log n)** - линейно-логарифмическая (быстрая сортировка) ``` sorted_list = sorted(my_list) # Timsort - O(n log n) ``` - **O(n²)** - квадратичная (пузырьковая сортировка) ``` for i in range(len(arr)): # O(n²) for j in range(len(arr)-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] ``` - **O(2ⁿ)** - экспоненциальная (рекурсивный Фибоначчи) ``` def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # O(2ⁿ) ``` - **O(n!)** - факториальная (перебор всех перестановок) Также существуют: - O(n³) - кубическая (наивное умножение матриц) - O(nᵏ) - полиномиальная - O(n√n) - встречается в некоторых алгоритмах