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

Оценки сложности алгоритмов описывают их эффективность по времени и памяти. Основные нотации:

• O(1) – константная сложность (доступ к элементу массива).
• O(log n) – логарифмическая (бинарный поиск).
• O(n) – линейная (проход по списку).
• O(n log n) – линейно-логарифмическая (быстрая сортировка).
• O(n²) – квадратичная (пузырьковая сортировка).
• O(2ⁿ) – экспоненциальная (рекурсивный Фибоначчи без кеширования).
• O(n!) – факториальная (перебор всех перестановок).

Пример:

# O(n) – линейный поиск
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

Память: Аналогичные оценки применяются для потребляемой памяти (например, O(n) для хранения списка из n элементов).