Какие знаешь типы сложности алгоритмов

Временная сложность алгоритмов описывает, как быстро растёт время выполнения с увеличением размера входных данных. Основные типы:

1. O(1) – константная сложность (доступ к элементу массива по индексу)

arr[5]  # O(1)

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

3. O(n) – линейная (поиск в неотсортированном массиве)

for item in arr:  # O(n)
    print(item)

4. O(n log n) – линейно-логарифмическая (быстрая сортировка, сортировка слиянием)

5. O(n²) – квадратичная (пузырьковая сортировка)

for i in range(n):  # O(n²)
    for j in range(n):
        print(i, j)

6. O(2^n) – экспоненциальная (рекурсивное вычисление чисел Фибоначчи)
7. O(n!) – факториальная (перебор всех перестановок)

Пространственная сложность аналогично описывает использование памяти.