Big O для памяти
Big O описывает память так же, как описывает время: сколько дополнительного места нужно алгоритму по мере роста входных данных?
Мы учитываем только дополнительное место — переменные и массивы, которые создаёт алгоритм, — а не сами входные данные. Это дополнительное место называют вспомогательной памятью.
Память O(1): фиксированное число переменных, независимо от входных данных. Память O(n): на каждый элемент входных данных сохраняется что-то новое — копия или ассоциативный массив увиденных значений.
Память O(1)
Алгоритм, который держит лишь несколько обычных переменных, использует константную память. Массив может содержать десять элементов или десять миллионов — самому алгоритму по-прежнему принадлежат только его счётчики.
Суммирование, поиск максимума и линейный поиск — всё это время O(n), но память O(1): они читают много, а запоминают почти ничего.
Сумма с одной переменной
Весь алгоритм помнит ровно одно число — $sum. Расход памяти не растёт вместе с массивом: память O(1).
Вывод: PHP-скрипт
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
// Одна дополнительная переменная, какой бы длинный ни был массив.
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
}
echo "сумма: ", $sum, "\n";
Память O(n)
Как только алгоритм строит что-то с одной записью на каждый элемент входных данных — новый массив, ассоциативный массив, — его память становится O(n): удвойте входные данные, и память удвоится.
Само по себе это не плохо. Это просто цена, которую стоит замечать, потому что её можно обменять.
Построение нового массива
Выходной массив получает по одному элементу на каждый элемент входных данных. 5 на входе, 5 на выходе — память растёт вместе с входными данными: память O(n).
Вывод: PHP-скрипт
<?php
$nums = [1, 2, 3, 4, 5];
// Новый массив с одним элементом на каждый элемент входных данных.
$doubled = [];
foreach ($nums as $n) {
$doubled[] = $n * 2;
}
echo "вход: ", implode(", ", $nums), "\n";
echo "выход: ", implode(", ", $doubled), "\n";
Обмен памяти на время
Часто можно потратить память, чтобы сэкономить время. Классический пример — Two Sum: найти в массиве два числа, дающих в сумме заданное значение.
Прямой способ проверяет каждую пару — время O(n²), память O(1). Быстрый способ проходит по массиву один раз и запоминает каждое увиденное число как ключ ассоциативного массива. Для каждого числа он спрашивает: «встречалось ли уже target - n?» — время O(n), память O(n).
Такой обмен обычно оправдан: память в машину добавить можно, время — нет.
Two Sum с двумя циклами
Каждая пара проверяется, пока не найдётся совпадение, — до 15 проверок для 6 элементов, и это число растёт как квадрат размера входных данных. Дополнительная память не используется.
Вывод: PHP-скрипт
<?php
$nums = [2, 11, 15, 1, 8, 7];
$target = 9;
$checks = 0;
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
$checks++;
if ($nums[$i] + $nums[$j] === $target) {
echo "найдено: ", $nums[$i], " + ", $nums[$j], " после ", $checks, " проверок\n";
}
}
}
echo "всего проверок: ", $checks, "\n";
Two Sum с ассоциативным массивом
Один проход, 6 проверок. Каждое число ищется с помощью isset() и сохраняется в ассоциативном массиве $seen — работа за константное время на элемент. Этот массив и есть память O(n), которая покупает время O(n).
Вывод: PHP-скрипт
<?php
$nums = [2, 11, 15, 1, 8, 7];
$target = 9;
$seen = [];
foreach ($nums as $n) {
$need = $target - $n;
if (isset($seen[$need])) {
echo "найдено: ", $need, " + ", $n, "\n";
}
$seen[$n] = true;
}
echo "проверено ", count($nums), " элементов по одному разу\n";