> Существует ли сложность алгоритмов по использованию памяти (Go)

Короткий ответ

Да, сложность алгоритмов по памяти существует и называется space complexity. Она измеряет объём дополнительной памяти, необходимой алгоритму, как функцию от размера входа. Обычно используется O-нотация. Важно различать auxiliary space и total space. В Go это особенно значимо из-за escape analysis, аллокаций в heap и сборщика мусора.

Подход к решению

Сначала определяем, что считаем входными данными, а что дополнительной памятью. Затем анализируем все аллокации: срезы, map, каналы, структуры, замыкания. Учитываем стек и heap. Для рекурсии считаем глубину стека. Для конкурентных программ учитываем память на горутины и буферы каналов. Оцениваем асимптотику в худшем, среднем и лучшем случае. Проверяем, можно ли переиспользовать память или работать in-place.

Пример кода

GO
package main

import "fmt"

// O(n) auxiliary space: создаёт новый срез
func reverseCopy(in []int) []int {
    out := make([]int, len(in))
    for i, v := range in {
        out[len(in)-1-i] = v
    }
    return out
}

// O(1) auxiliary space: in-place
func reverseInPlace(in []int) {
    for i, j := 0, len(in)-1; i < j; i, j = i+1, j-1 {
        in[i], in[j] = in[j], in[i]
    }
}

func main() {
    a := []int{1, 2, 3, 4}
    b := reverseCopy(a)
    reverseInPlace(a)
    fmt.Println(a, b)
}

Edge cases

Пустой вход и вход из одного элемента. Очень большой вход, где O(n) памяти может привести к OOM. Рекурсия с глубиной n, которая может переполнить стек. Срезы, разделяющие underlying array, что влияет на фактическое потребление памяти. Замыкания, захватывающие переменные и продлевающие их жизнь. Горутины и каналы с буферами, создающие неочевидные аллокации. Интернирование строк и слайсы байтов.

Как отвечать на собеседовании

Скажите, что space complexity - это отдельная метрика наряду с time complexity. Уточните, считаете ли вы auxiliary или total space. Приведите пример in-place алгоритма и его антипода. Упомяните особенности Go: escape analysis, heap, GC, слайсы. Покажите, что умеете оценивать память для рекурсии и конкурентности. Предложите trade-off между временем и памятью.

Что проверяет интервьюер

Понимание асимптотического анализа памяти. Умение различать auxiliary и total space. Знание особенностей управления памятью в Go. Способность писать in-place алгоритмы. Навык оценивать рекурсию и конкурентность по памяти. Осознание trade-off между временем и памятью. Практический опыт борьбы с OOM и оптимизацией аллокаций.