Big O для памяти
Big O может описывать память так же, как описывает время: сколько дополнительной памяти нужно алгоритму по мере роста входных данных?
Мы считаем только дополнительную память — переменные и срезы, которые создаёт алгоритм, — а не сами входные данные. Эту дополнительную память называют вспомогательной памятью.
Память O(1): фиксированное число переменных, независимо от входных данных. Память O(n): на каждый входной элемент сохраняется что-то новое, например копия или map уже встреченных значений.
Память O(1)
Алгоритм, который хранит лишь несколько простых переменных, использует константную память. В срезе может быть десять элементов или десять миллионов — самому алгоритму по-прежнему принадлежат только его счётчики.
Суммирование, поиск максимума и линейный поиск — всё это время O(n), но память O(1): они много читают и почти ничего не запоминают.
Сумма с одной переменной
Весь алгоритм запоминает ровно одно число — sum. Расход памяти не растёт вместе со срезом: память O(1).
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
// Одна дополнительная переменная, какой бы длины ни был срез.
sum := 0
for _, n := range nums {
sum += n
}
fmt.Println("сумма:", sum)
}
Память O(n)
Как только алгоритм строит что-то, где на каждый входной элемент приходится своя запись — новый срез, map, — его память становится O(n): вдвое больше входных данных — вдвое больше памяти.
Само по себе это не плохо. Это просто цена, которую стоит замечать, потому что её можно обменивать.
Построение нового среза
Выходной срез получает по одному элементу на каждый входной элемент. 5 на входе, 5 на выходе — память растёт вместе с входными данными: память O(n).
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{1, 2, 3, 4, 5}
// Новый срез с одним элементом на каждый входной элемент.
doubled := make([]int, 0, len(nums))
for _, n := range nums {
doubled = append(doubled, n*2)
}
fmt.Println("вход: ", nums)
fmt.Println("выход:", doubled)
}
Обмен памяти на время
Часто память можно потратить, чтобы сэкономить время. Классический пример — Two Sum: найти в срезе два числа, которые в сумме дают заданное значение.
Прямой способ проверяет каждую пару — время O(n²), память O(1). Быстрый способ проходит по срезу один раз и запоминает в map каждое встреченное число. Для каждого числа он спрашивает: «встречалось ли уже target - n?» — время O(n), память O(n).
Такой обмен обычно оправдан: память в машину можно добавить, а время — нет.
Two Sum с двумя циклами
Проверяется каждая пара, пока не найдётся совпадение, — до 15 проверок для 6 элементов, и это число растёт как квадрат размера входных данных. Дополнительная память не используется.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{2, 11, 15, 1, 8, 7}
target := 9
checks := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
checks++
if nums[i]+nums[j] == target {
fmt.Println("найдено:", nums[i], "+", nums[j], "после", checks, "проверок")
}
}
}
fmt.Println("всего проверок:", checks)
}
Two Sum с map
Один проход, 6 проверок. Каждое число ищется и сохраняется в map seen — работа за константное время на элемент. Этот map и есть память O(n), которая покупает время O(n).
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{2, 11, 15, 1, 8, 7}
target := 9
seen := map[int]bool{}
for _, n := range nums {
if seen[target-n] {
fmt.Println("найдено:", target-n, "+", n)
}
seen[n] = true
}
fmt.Println("проверено", len(nums), "элементов по одному разу")
}