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

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

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

def get_first(arr):
    return arr[0]  # Всегда один шаг

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
        else:
            high = mid - 1

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

def linear_search(arr, x):
    for item in arr:
        if item == x:
            return True

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

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

6. O(2ⁿ) – экспоненциальная (рекурсивные вычисления Фибоначчи)

7. O(n!) – факториальная (перебор всех перестановок)

Также существуют пространственные сложности, описывающие использование памяти.