Big O для памяти
Big O может описывать память так же, как описывает время: сколько дополнительного места нужно алгоритму по мере роста входных данных?
Мы считаем только дополнительное место — переменные и массивы, которые создаёт алгоритм, — а не сами входные данные. Это дополнительное место называют вспомогательной памятью.
Память O(1): фиксированное количество переменных, каким бы ни был вход. Память O(n): на каждый входной элемент сохраняется что-то новое, например копия или Map уже увиденных значений.
Память O(1)
Алгоритм, который хранит лишь несколько обычных переменных, использует постоянную память. В массиве может быть десять элементов или десять миллионов — самому алгоритму по-прежнему принадлежат только его счётчики.
Суммирование, поиск максимума и линейный поиск — все они имеют время O(n), но память O(1): они читают много, а запоминают почти ничего.
Сумма с одной переменной
Весь алгоритм помнит ровно одно число — sum. Его расход памяти не растёт вместе с массивом: память O(1).
Вывод: программа на TypeScript и захваченный вывод
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
// Одна дополнительная переменная, независимо от длины массива.
let sum = 0
for (const n of nums) {
sum += n
}
console.log("сумма:", sum)
Память O(n)
Как только алгоритм строит что-то с одной записью на каждый входной элемент — новый массив, Map, — его память становится O(n): удвойте вход, и память удвоится.
Само по себе это не плохо. Это просто цена, которую стоит замечать, потому что её можно обменять.
Построение нового массива
Выходной массив получает по одному элементу на каждый входной элемент. 5 на входе, 5 на выходе — память растёт вместе с входом: память O(n).
Вывод: программа на TypeScript и захваченный вывод
const nums = [1, 2, 3, 4, 5]
// Новый массив с одним элементом на каждый входной элемент.
const doubled: number[] = []
for (const n of nums) {
doubled.push(n * 2)
}
console.log("вход: ", nums)
console.log("выход:", doubled)
Обмен памяти на время
Часто можно потратить память, чтобы сэкономить время. Классический пример — Two Sum: найти в массиве два числа, дающих в сумме заданное значение.
Прямой способ проверяет каждую пару — время O(n²), память O(1). Быстрый способ проходит по массиву один раз и запоминает каждое увиденное число в Map. Для каждого числа он спрашивает: «встречалось ли уже target - n?» — время O(n), память O(n).
Такой обмен обычно оправдан: память в машину добавить можно, а время — нет.
Two Sum с двумя циклами
Каждая пара проверяется, пока не найдётся совпадение — до 15 проверок для 6 элементов, и это число растёт как квадрат входа. Дополнительная память не используется.
Вывод: программа на TypeScript и захваченный вывод
const nums = [2, 11, 15, 1, 8, 7]
const target = 9
let checks = 0
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
checks++
if (nums[i] + nums[j] === target) {
console.log("найдено:", nums[i], "+", nums[j], "после", checks, "проверок")
}
}
}
console.log("всего проверок:", checks)
Two Sum с Map
Один проход, 6 проверок. Каждое число ищется через seen.has() и сохраняется через seen.set() — работа за постоянное время на элемент. Map — это та память O(n), которая покупает время O(n).
Вывод: программа на TypeScript и захваченный вывод
const nums = [2, 11, 15, 1, 8, 7]
const target = 9
// Одна запись на каждый уже увиденный элемент: это и есть память O(n).
const seen = new Map<number, boolean>()
for (const n of nums) {
if (seen.has(target - n)) {
console.log("найдено:", target - n, "+", n)
}
seen.set(n, true)
}
console.log("проверено", nums.length, "элементов по одному разу")