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

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

Понимаете ли вы, что это про рост при увеличении входа, а не про скорость в секундах.

Как отвечать

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

Обозначения: O это верхняя граница (чаще всего используют её), Ω нижняя, Θ точная. Константы и младшие слагаемые отбрасываются, потому что при большом входе они не влияют: 3n² + 100n это O(n²).

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

Основные классы: O(1) доступ по индексу и в карту, O(log n) двоичный поиск и дерево, O(n) проход по срезу, O(n log n) сортировка сравнением, O(n²) вложенный цикл по той же коллекции, O(2^n) перебор подмножеств.

Практика в Go, где это чаще всего встречается:

• поиск по срезу внутри цикла даёт квадрат. Замена на карту делает линейным;
• склейка строк в цикле через + создаёт новую строку каждый раз, отсюда квадрат по памяти и времени. Нужен strings.Builder;
• append без предварительной ёмкости вызывает несколько перевыделений. make([]T, 0, n) их убирает;
• удаление из середины среза это O(n) со сдвигом.

Обязательная оговорка про реальность: асимптотика описывает поведение на больших данных. На маленьких константы решают всё, и линейный проход по срезу нередко быстрее карты за счёт того, что данные лежат подряд и попадают в кэш процессора. Поэтому вывод делают по замеру (go test -bench), а асимптотика нужна, чтобы понимать, что произойдёт при росте в сто раз.

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

Называют O(n) временем выполнения в секундах.

Забывают про сложность по памяти.

Не замечают скрытый вложенный проход внутри вызываемой функции.

Оптимизируют асимптотику там, где вход всегда мал.