Не доверяйте нотации Big-O
если у вас есть массив между 12–15 элементами, используйте сортировку вставками.
Хорошо известно, что временная сложность при использовании обозначения Big-O для наихудшего случая сортировки вставками составляет O(n²).
Однако нотация Big-O касается только асимптотической эффективности алгоритма. Это означает, что мы рассматриваем производительность алгоритма только тогда, когда размер входных данных близок к пределу его эффективности.
Иногда размер нашей проблемы далеко не предел, и мы можем найти простое решение.
Постоянные факторы и младшие члены
В нотации Big-O учитывается только начальный термин. Он опускает постоянные коэффициенты и члены более низкого порядка.
Давайте сравним две функции, старшие члены которых n²
Обе функции будут O(n²), но очевидно, что n² будет быстрее, чем 2n².
Логарифмический против квадрата
Вместо сортировки вставками вы можете использовать сортировку кучей, временная сложность Big-O которой равна O(nlogn):
Мы будем использовать алгоритм сортировки кучей только в том случае, если будем рассматривать только ведущие члены. Но некоторые гибридные алгоритмы используют сортировку вставками.
Быстрая сортировка, отключающая шаблон, разбивает входной массив на несколько подмассивов. В реализации Golang, если один из этих подмассивов содержит 12 или менее элементов, вместо быстрой сортировки используется сортировка вставками.
Мы можем воспроизвести это поведение на наших графиках, включив некоторые постоянные факторы и члены более низкого порядка:
Логарифмическая функция становится лучше квадратичной только после 15. Нечто подобное происходит и с сортировкой вставками, что делает ее лучшим алгоритмом сортировки для небольших массивов.
Заключение
Хотя сложность Big-O показывает нам производительность определенного алгоритма, этолишь полуправда.
Как мы видим, сортировка вставками занимает место между другими алгоритмами. Библиотека сортировки вашего любимого языка программирования, вероятно, использует ее под капотом.
Для программистов это урок.
Если вы освоите свои инструменты и поймете свою проблему, решение может быть простым.
