Эффективность алгоритма с точки зрения потребления памяти измеряется через пространственную сложность. 12 Она определяет объём памяти, которую использует алгоритм в зависимости от размера входных данных. 1

На пространственную сложность влияют несколько факторов, включая количество переменных, тип и размер структуры данных, вызовы функций и способ выделения памяти. 1

Для оценки пространственной сложности используется обозначение Big O. 2 Оно позволяет оценить, как время выполнения алгоритма или требуемый объём памяти растут с увеличением размера входных данных. 1

Некоторые общие виды пространственной сложности:

• O(1) — константное пространство. 1 Алгоритм использует фиксированный объём памяти независимо от размера входных данных. 2
• O(n) — линейное пространство. 2 Использование памяти растёт линейно с увеличением размера входных данных. 2
• O(n^2) — квадратичное пространство. 2 Использование памяти растёт квадратично с увеличением размера входных данных. 2