Что такое временная сложность алгоритмов и как она измеряется

Что проверяют

Умеете ли вы оценивать алгоритм до запуска и отличаете ли асимптотику от замера. За вопросом стоит практический навык: по коду сказать, как вырастет время при росте данных, и понять, где настоящее узкое место, а где экономия на спичках.

Как отвечать

Временная сложность это зависимость числа элементарных операций от размера входа, а не время в секундах: константы, железо и компилятор она сознательно отбрасывает. Записывают её асимптотикой: O задаёт верхнюю границу, Ω нижнюю, Θ точную; на собеседовании обычно говорят O, подразумевая Θ.

Дальше стоит развести случаи: худший, средний и амортизированный. Готовый пример из Go это append: отдельная вставка может вызвать перевыделение и копирование всего среза, но ёмкость растёт кратно, поэтому средняя стоимость вставки константна. Доступ в map тоже средний O(1), а не гарантированный.

Полезно показать счёт по коду: вложенный цикл по срезу даёт O(n²), поиск перебором O(n) против множества на map за O(1), sort.Slice даёт O(n log n). Склейка строк в цикле квадратична, потому что строка неизменяема и каждый шаг копирует накопленное:

var b strings.Builder
for _, s := range parts {
    b.WriteString(s)
}

Закончить стоит тем, что асимптотика не отменяет измерения: go test -bench и профиль показывают ту константу, которую формула прячет.

Где спотыкаются

Путают сложность со временем работы и объявляют O(n) синонимом слова «быстро». Асимптотика сравнивает рост, а не абсолютные числа: на реальных размерах решение за O(n log n) без аллокаций обгоняет линейный проход, который на каждом шаге ходит в кучу.

Считают только видимые циклы. Вызов внутри цикла тоже имеет цену: сортировка в теле, copy, конкатенация, поиск подстроки. Одна такая строка превращает линейный проход в квадратичный, а в коде это не бросается в глаза.

Молчат про память. У алгоритма есть и пространственная сложность, а в Go к ней добавляется давление на сборщик мусора: вариант с предвыделенным срезом и вариант с ростом по одному элементу совпадают по асимптотике времени и расходятся на практике.