Что такое пространственная сложность (space complexity) алгоритма?

Пространственная сложность (space complexity) — это метрика, которая оценивает объем памяти, необходимый алгоритму для выполнения, как функцию от размера входных данных (n).

Она складывается из двух компонентов:

• Входное пространство (Input Space): Память, необходимая для хранения входных данных.
• Вспомогательное пространство (Auxiliary Space): Дополнительная ("рабочая") память, которую алгоритм использует во время выполнения (переменные, структуры данных).

Чаще всего под пространственной сложностью понимают именно вспомогательное пространство, так как оно характеризует эффективность самого алгоритма.

Примеры:

# O(1) - константная сложность
def get_sum(arr):
    total = 0 # Одна переменная
    for num in arr:
        total += num
    return total
    # Память не зависит от размера arr

# O(n) - линейная сложность
def reverse_array(arr):
    # Новый массив того же размера, что и входной
    return arr[::-1]
    # Потребление памяти растет линейно с размером arr

Основные классы сложности:

• O(1): Константная (например, простые арифметические операции).
• O(log n): Логарифмическая (например, некоторые рекурсивные алгоритмы).
• O(n): Линейная (например, создание копии массива).
• O(n²): Квадратичная (например, создание матрицы n x n).

Анализ пространственной сложности критически важен при работе с большими объемами данных или в средах с ограниченной памятью (например, в embedded-системах).