Что такое пространственная сложность алгоритма

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

Примеры:

# O(1) - константная сложность
def sum_two(a, b):
    return a + b  # всегда использует фиксированное кол-во памяти

# O(n) - линейная сложность
def create_list(n):
    return [0] * n  # память растет линейно с n

Основные случаи:

• O(1) — константная (не зависит от ввода)
• O(n) — линейная
• O(n²) — квадратичная
• O(log n) — логарифмическая

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