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

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

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

Что именно измеряется?

Пространственная сложность показывает:

1. Дополнительную память для вспомогательных структур данных (не учитывая входные данные)
2. Рекурсивный стек вызовов при рекурсивных алгоритмах
3. Расширяемые структуры (списки, словари) по мере роста входных данных
4. Промежуточные результаты вычислений

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

Нотация Big O для памяти

Сложность по памяти обозначается так же, как и временная сложность:

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

Примеры анализа

Пример 1: O(1) — константная память

def find_max(arr):
    max_val = arr[0]  # Одна переменная
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

# Сложность по памяти: O(1)
# Используем фиксированное количество переменных

Пример 2: O(n) — линейная память

def reverse_array(arr):
    reversed_arr = []  # Создаём новый массив
    for i in range(len(arr) - 1, -1, -1):
        reversed_arr.append(arr[i])
    return reversed_arr

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

Пример 3: O(n) — рекурсия

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Сложность по памяти: O(n)
# Каждый рекурсивный вызов добавляет фрейм в стек вызовов
# Глубина стека: n фреймов

Пример 4: O(n²) — квадратичная память

def create_matrix(n):
    matrix = []
    for i in range(n):
        row = []
        for j in range(n):
            row.append(i * j)
        matrix.append(row)
    return matrix

# Сложность по памяти: O(n²)
# Выделяем память для матрицы размером n×n элементов

Пример 5: O(n log n) — сортировка слиянием

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # Копия массива: O(n)
    right = merge_sort(arr[mid:])     # Копия массива: O(n)
    
    return merge(left, right)

# Сложность по памяти: O(n log n)
# Глубина рекурсии: O(log n), на каждом уровне: O(n)

Оптимизация памяти

In-place алгоритмы — модифицируют входные данные вместо создания копий:

# Плохо: O(n) дополнительной памяти
def reverse_bad(arr):
    return arr[::-1]  # Создаёт копию

# Хорошо: 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

Trade-off: время vs память

Часто между временной и пространственной сложностью существует компромисс:

# Быстро, но больше памяти: O(n) память
def count_duplicates_hashmap(arr):
    counts = {}
    for num in arr:
        counts[num] = counts.get(num, 0) + 1
    return counts

# Медленнее, но меньше памяти: O(1) память
def count_duplicates_sorting(arr):
    arr.sort()  # Модифицируем входные данные
    # Подсчитываем совпадающие элементы

Практическое значение

Анализ пространственной сложности важен:

• На мобильных и встроенных системах с ограниченной памятью
• При обработке больших объёмов данных
• В облачных приложениях, где память — дорогостоящий ресурс
• При оптимизации кэша процессора