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

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

Умеете ли вы оценивать код, который пишете каждый день, а не пересказывать таблицу из учебника. Для Go вопрос очень предметный: у слайсов, карт и строк своя стоимость операций, и на собеседовании обычно просят оценить не абстрактный алгоритм, а конкретную функцию.

Как отвечать

Нотация описывает, как растёт время или память при росте размера входа, отбрасывая константы и младшие слагаемые. Большое O это верхняя граница, омега нижняя, тета оценка сверху и снизу одновременно. Привычка говорить O там, где имеется в виду тета, распространена, но на уточнение «а верно ли, что бинарный поиск это O(n^2)» правильный ответ звучит так: формально верно, только оценка бесполезна.

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

Дальше самый частый практический пример на Go.

var s string
for _, x := range parts {
    s += x // O(n^2): строки неизменяемы, каждый шаг копирует накопленное
}

var b strings.Builder
b.Grow(total)
for _, x := range parts {
    b.WriteString(x) // амортизированная O(1) на элемент
}

Хорошо добавить про память: она считается так же, и рекурсия глубиной n стоит O(n) стека. И про то, что асимптотика не отменяет замер: на малых входах линейный проход по слайсу обгоняет карту, потому что константа и промахи кэша решают больше, чем степень.

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

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

Забывают про стоимость скрытых операций. Копирование слайса, сортировка внутри цикла, поиск подстроки в длинной строке в теле обхода стоят столько же, сколько явный вложенный цикл.

Уверенно называют сложность, но не могут сказать, для какого случая. Быстрая сортировка это O(n log n) в среднем и O(n^2) в худшем, и разницу спрашивают именно тогда, когда кандидат отвечает слишком гладко.