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

Пространственная сложность алгоритма

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

Основной концепт

Пространственная сложность измеряется в O-нотации (Big O Notation) и указывает на асимптотическое поведение использования памяти:

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

Примеры пространственной сложности

O(1) — Константная сложность

def sum_first_and_last(arr):
    # Используем только 2 переменные, независимо от размера массива
    first = arr[0]
    last = arr[-1]
    return first + last

# Пространственная сложность: O(1)
# Память: всегда 2 переменные, независимо от n

O(n) — Линейная сложность

def create_copy(arr):
    # Создаем новый массив размером n
    copy = []
    for item in arr:
        copy.append(item)
    return copy

# Пространственная сложность: O(n)
# Если n = 1000, то новый массив займет память для 1000 элементов

O(n²) — Квадратичная сложность

def create_matrix(n):
    # Создаем матрицу n x n
    matrix = []
    for i in range(n):
        row = []
        for j in range(n):
            row.append(i * j)
        matrix.append(row)
    return matrix

# Пространственная сложность: O(n²)
# Матрица 10x10 = 100 элементов
# Матрица 100x100 = 10000 элементов

O(log n) — Логарифмическая сложность

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        # Рекурсивный вызов — добавляет в стек вызовов
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# Пространственная сложность: O(log n)
# Стек вызовов растет логарифмически
# При n = 1000000, глубина стека ~ 20

Сравнение временной и пространственной сложности

# Временная O(n), пространственная O(1)
def find_max(arr):
    max_val = arr[0]
    for item in arr:
        if item > max_val:
            max_val = item
    return max_val

# Временная O(n), пространственная O(n)
def create_doubled(arr):
    result = []
    for item in arr:
        result.append(item * 2)
    return result

# Временная O(n²), пространственная O(1)
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Временная O(n log n), пространственная O(n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # Новый массив O(n/2)
    right = merge_sort(arr[mid:])     # Новый массив O(n/2)
    return merge(left, right)         # Результат O(n)

Анализ стека вызовов

Рекурсия значительно влияет на пространственную сложность:

# Пространственная сложность: O(n)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # n вложенных вызовов в стеке

# factorial(5):
# factorial(4) - в стеке
#   factorial(3) - в стеке
#     factorial(2) - в стеке
#       factorial(1) - в стеке
#         return 1
# Максимум n элементов в стеке одновременно

Оптимизация пространственной сложности

Плохо: создание новых структур

# O(n) пространственная сложность
def reverse_bad(arr):
    new_arr = []
    for i in range(len(arr) - 1, -1, -1):
        new_arr.append(arr[i])
    return new_arr

Хорошо: in-place операции

# O(1) пространственная сложность
def reverse_good(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Практический пример: хеш таблица vs список

# Поиск элемента — O(n) временная, O(1) пространственная
def find_in_list(lst, value):
    for item in lst:
        if item == value:
            return True
    return False

# Поиск элемента — O(1) временная, O(n) пространственная
def find_in_set(lst, value):
    s = set(lst)  # Создаем set — O(n) памяти
    return value in s  # Поиск — O(1) времени

Таблица сложностей часто используемых операций

Когда пространственная сложность критична

• Встроенные системы с ограниченной памятью
• Обработка больших данных (миллионы элементов)
• Мобильные приложения с ограниченным RAM
• Работа с видео/аудио потоками (не можем хранить все в памяти)

Резюме

Пространственная сложность — это анализ использования памяти алгоритмом. Как и временная сложность, она выражается в O-нотации. При выборе алгоритма нужно балансировать между временной и пространственной сложностью. Часто оптимальное решение — использовать больше памяти, чтобы сэкономить время (или наоборот).