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

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

Понимаете ли вы, что оценка описывает рост, а не время в секундах, и знаете ли, зачем нужны разные случаи.

Как отвечать

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

Обозначения:

• O это верхняя граница, «растёт не быстрее чем». Используется чаще всего;
• Ω нижняя граница;
• Θ точная оценка, когда верхняя и нижняя совпадают.

Константы и младшие слагаемые отбрасываются: 3n² + 100n + 5 это O(n²), потому что при большом входе решает старший член.

Оценивают отдельно время и память. Сортировка слиянием и пирамидальная обе дают O(n log n) по времени, но первая требует O(n) дополнительной памяти, а вторая O(1).

Случаи различают три:

• худший: гарантия, обычно её и называют;
• средний: по распределению входных данных. Например быстрая сортировка в среднем O(n log n), а в худшем O(n²);
• амортизированный: редкая дорогая операция размазывается по дешёвым. Добавление в ArrayList это O(1) амортизированно, хотя изредка копируется весь массив.

Основные классы: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).

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

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

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

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

Не различают худший и средний случай.

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