EasyТеория19 min

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

Анализ потребления памяти: стек вызовов, вспомогательные структуры, in-place алгоритмы

AlgoBasics

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

Пространственная сложность — это количество дополнительной памяти, которую использует алгоритм в зависимости от размера входных данных. Мы измеряем auxiliary space — память сверх входных данных.

Два вида пространственной сложности:

  • Total space = входные данные + дополнительная память
  • Auxiliary space = только дополнительная память (обычно это то, что нас интересует)

Из чего складывается потребление памяти

1. Переменные и примитивы

function example(int $n): void
{
    $x = 5;           // O(1) — one number
    $name = 'hello';  // O(1) — fixed string
    $flag = true;     // O(1) — boolean
    // All together: O(1)
}
### 2. Структуры данных 
function example(int $n): void
{
    $arr = array_fill(0, $n, 0);     // O(n) — array of size n
    $matrix = [];
    for ($i = 0; $i < $n; $i++) {
        $matrix[$i] = array_fill(0, $n, 0); // O(n²) — matrix n x n
    }
    $map = [];                        // O(k), where k — number of added elements
}
### 3. Стек вызовов (рекурсия) 
function recursive(int $n): void
{
    if ($n <= 0) {
        return;
    }
    recursive($n - 1);
}
// Call stack: n frames -> O(n) memory
Визуализация стека вызовов для `recursive(4)`: 
Стек вызовов (растёт вниз):

| recursive(4) |  <- первый вызов
| recursive(3) |
| recursive(2) |
| recursive(1) |
| recursive(0) |  <- базовый случай, начинаем возвращаться

Каждый фрейм в стеке хранит:

  • Локальные переменные
  • Параметры функции
  • Адрес возврата

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

O(1) — константная память

// Find maximum — only one variable
function findMax(array $arr): int
{
    $maxVal = $arr[0];       // O(1) extra memory
    foreach ($arr as $x) {
        if ($x > $maxVal) {
            $maxVal = $x;
        }
    }
    return $maxVal;
}

// Reverse array in-place — O(1)
function reverseInplace(array &$arr): void
{
    $left = 0;
    $right = count($arr) - 1;
    while ($left < $right) {
        [$arr[$left], $arr[$right]] = [$arr[$right], $arr[$left]];
        $left++;
        $right--;
    }
    // Array modified, no extra memory allocated
}
---

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

// Creating a new array
function doubleValues(array $arr): array
{
    $result = [];              // New array
    foreach ($arr as $x) {
        $result[] = $x * 2;
    }
    return $result;            // result holds n elements -> O(n)
}

// Hash table for frequency counting
function frequencyCount(array $arr): array
{
    $freq = [];                // Worst case: n unique elements
    foreach ($arr as $x) {
        $freq[$x] = ($freq[$x] ?? 0) + 1;
    }
    return $freq;              // O(n)
}
---

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

// Adjacency matrix of a graph
function createAdjacencyMatrix(int $n): array
{
    $matrix = [];
    for ($i = 0; $i < $n; $i++) {
        $matrix[$i] = array_fill(0, $n, 0); // n x n -> O(n²)
    }
    return $matrix;
}

// All pair sums (for caching results)
function allPairSums(array $arr): array
{
    $n = count($arr);
    $result = [];
    for ($i = 0; $i < $n; $i++) {
        $result[$i] = array_fill(0, $n, 0);
        for ($j = 0; $j < $n; $j++) {
            $result[$i][$j] = $arr[$i] + $arr[$j];
        }
    }
    return $result; // O(n²)
}
---

Рекурсия и стек вызовов

// Linear recursion: O(n) memory
function sumRecursive(array $arr, int $index = 0): int
{
    if ($index === count($arr)) {
        return 0;
    }
    return $arr[$index] + sumRecursive($arr, $index + 1);
}
// Stack: n frames -> O(n)

// Recursion with two branches: O(n) memory (not O(2^n)!)
function fib(int $n): int
{
    if ($n <= 1) {
        return $n;
    }
    return fib($n - 1) + fib($n - 2);
}
// Time: O(2^n), but MEMORY: O(n)
// Because the stack holds only ONE branch at a time!
Это важный момент! Дерево рекурсии Фибоначчи имеет O(2^n) узлов, но максимальная глубина стека — n: 
Стек в момент самого глубокого вызова fib(5):

Шаг 1: fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1)
Стек:  [fib(5), fib(4), fib(3), fib(2), fib(1)]  — глубина 5

Шаг 2: fib(1) вернул 1, fib(2) вызывает fib(0)
Стек:  [fib(5), fib(4), fib(3), fib(2), fib(0)]  — глубина 5

Максимальная глубина стека = n -> O(n) по памяти

// Tail recursion (PHP does NOT optimize it)
function sumTail(array $arr, int $index = 0, int $acc = 0): int
{
    if ($index === count($arr)) {
        return $acc;
    }
    return sumTail($arr, $index + 1, $acc + $arr[$index]);
}
// Theoretically O(1), but PHP still uses O(n) stack

// Iterative version — O(1) memory
function sumArray(array $arr): int
{
    $acc = 0;
    foreach ($arr as $x) {
        $acc += $x;
    }
    return $acc;
}
## In-place алгоритмы

In-place алгоритм использует O(1) дополнительной памяти (или O(log n) для рекурсии).

Пример: сортировка вставками — in-place

function insertionSort(array &$arr): void
{
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    // Original array modified
    // Extra memory: O(1) (variables $key, $i, $j)
}
### Пример: merge sort — НЕ in-place 
function mergeSort(array $arr): array
{
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $mid));   // Creates new array!
    $right = mergeSort(array_slice($arr, $mid));       // Creates new array!
    return merge($left, $right);                       // Another array!
}
// Extra memory: O(n) for merging + O(log n) stack = O(n)
### Сравнение: in-place vs not in-place
Алгоритм Время Доп. память In-place?
Bubble Sort O(n²) O(1) Да
Insertion Sort O(n²) O(1) Да
Selection Sort O(n²) O(1) Да
Merge Sort O(n log n) O(n) Нет
Quick Sort O(n log n) O(log n)* Да
Heap Sort O(n log n) O(1) Да
Counting Sort O(n + k) O(k) Нет

* — O(log n) для стека рекурсии

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

Часто можно обменять память на скорость и наоборот.

Пример: проверка дубликатов

// Approach 1: O(1) memory, O(n²) time
function hasDupBrute(array $arr): bool
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$i] === $arr[$j]) {
                return true;
            }
        }
    }
    return false;
}

// Approach 2: O(n) memory, O(n) time
function hasDupSet(array $arr): bool
{
    $seen = [];
    foreach ($arr as $x) {
        if (isset($seen[$x])) {
            return true;
        }
        $seen[$x] = true;
    }
    return false;
}

// Approach 3: O(1) memory*, O(n log n) time
function hasDupSort(array &$arr): bool
{
    sort($arr); // Modifies the original array!
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] === $arr[$i - 1]) {
            return true;
        }
    }
    return false;
}
### Пример: Two Sum 
// Approach 1: O(1) memory, O(n²) time
function twoSumBrute(array $arr, int $target): array
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$i] + $arr[$j] === $target) {
                return [$i, $j];
            }
        }
    }
    return [];
}

// Approach 2: O(n) memory, O(n) time
function twoSumHash(array $arr, int $target): array
{
    $seen = [];
    foreach ($arr as $i => $num) {
        $complement = $target - $num;
        if (isset($seen[$complement])) {
            return [$seen[$complement], $i];
        }
        $seen[$num] = $i;
    }
    return [];
}
## Частые ловушки

Ловушка 1: срезы массива создают копии

function process(array $arr): void
{
    $half = array_slice($arr, 0, intdiv(count($arr), 2)); // Creates a COPY! O(n) memory
    // ...
}

// Better: use indices
function processInplace(array $arr, int $start, int $end): void
{
    for ($i = $start; $i < $end; $i++) {
        // work with $arr[$i]
    }
}
### Ловушка 2: Конкатенация строк 
// O(n²) memory and time!
function buildStringBad(int $n): string
{
    $result = '';
    for ($i = 0; $i < $n; $i++) {
        $result .= $i; // Creates a new string each time!
    }
    return $result;
}

// O(n) — correct approach
function buildStringGood(int $n): string
{
    $parts = [];
    for ($i = 0; $i < $n; $i++) {
        $parts[] = $i;
    }
    return implode('', $parts);
}
### Ловушка 3: Рекурсия на больших данных 
// May cause StackOverflow for large n
function deepRecursion(int $n): int
{
    if ($n <= 0) {
        return 0;
    }
    return 1 + deepRecursion($n - 1);
}

// Solution: iterative version
function iterativeVersion(int $n): int
{
    $count = 0;
    while ($n > 0) {
        $count++;
        $n--;
    }
    return $count;
}
## Таблица: память для типичных структур данных
Структура Память
Массив (n элементов) O(n)
Матрица (n x m) O(n*m)
HashMap (n пар) O(n)
Связный список (n узлов) O(n)
Бинарное дерево (n узлов) O(n)
Стек рекурсии (глубина d) O(d)
Граф (V вершин, E рёбер) O(V + E)
Trie (с p символами) O(p * alphabet_size)

Запомни: Пространственная сложность — это не только явные структуры данных. Не забывай про стек вызовов при рекурсии! Рекурсия с глубиной n потребляет O(n) памяти, даже если вы не создаёте массивов. Когда выбираешь между решениями — учитывай trade-off между временем и памятью.

Итоги

  1. Считай дополнительную память, а не входные данные
  2. Стек рекурсии = O(глубина рекурсии) памяти
  3. In-place алгоритмы: O(1) доп. памяти
  4. Срезы и конкатенация строк создают копии — осторожно!
  5. Trade-off: часто можно обменять O(n) памяти на ускорение с O(n²) до O(n)
  6. Для больших данных предпочитай итерацию рекурсии

Проверь себя

5 из 8

PHP не оптимизирует хвостовую рекурсию. Что это значит на практике?

Какой из подходов к проверке дубликатов использует O(1) дополнительной памяти?

В Go оптимизации хвостовых вызовов нет. Чем тогда ограничена глубина рекурсии в горутине?

Merge Sort имеет временную сложность O(n log n). Какова его пространственная сложность?

Какова пространственная сложность наивной рекурсивной функции Фибоначчи fib(n)?

Связанные темы

Стратегия на интервью

Связанная тема