Какие бывают виды алгоритмической сложности?
Что проверяют
Понимаете ли вы, что оценка про скорость роста, а не про секунды, и можете ли привязать классы к знакомым алгоритмам.
Как отвечать
Сложность описывает, как растёт число операций при росте размера входа. Записывается O-нотацией и отбрасывает константы: важен порядок, а не множитель.
Основные классы по возрастанию:
- O(1): доступ по индексу, вставка в хеш-таблицу;
- O(log n): бинарный поиск, поиск в сбалансированном дереве. Миллион элементов это двадцать шагов;
- O(n): один проход по массиву, поиск максимума;
- O(n log n): хорошие сортировки, merge sort и quicksort в среднем. Ниже для сортировки сравнениями не бывает;
- O(n²): вложенные циклы, пузырьковая сортировка, попарное сравнение;
- O(2ⁿ) и O(n!): перебор подмножеств и перестановок, применимо только на очень малых входах.
Отдельно считается сложность по памяти: сортировка на месте это O(1) дополнительной памяти, merge sort требует O(n).
Полезно упомянуть, что бывают лучший, средний и худший случаи, и они расходятся: у quicksort в среднем O(n log n), в худшем O(n²). А ещё есть амортизированная оценка: append в динамический массив это O(1) в среднем, хотя отдельная вставка с перевыделением стоит O(n).
Где спотыкаются
Называют классы, но не могут привязать ни один к конкретному алгоритму.
Считают, что O(1) значит быстро. Это значит независимо от размера входа, константа может быть большой.
Забывают про память и оценивают только время.
Не различают худший и средний случай, из-за чего не могут объяснить, почему quicksort используют чаще merge sort.