Никита Нагорнов. O(n) проиграл O(n log n): ваш алгоритм не выбирал процессор, на котором работает

Почему ожидаемо линейный алгоритм может проиграть сортировке? На примере дедупликации разберём, как кэши, аллокации, распределение данных и выбранное планировщиком ядро меняют победителя. Один C++20-код испытаем на x86-64, Apple Silicon и мобильных ARM64-устройствах. Big-O описывает рост, но не время конкретного запуска. sort + unique иногда быстрее хеш-таблицы благодаря последовательной памяти. Даже две хеш-таблицы с одинаковой сложностью могут отличаться в разы. На смартфоне результат зависит от типа ядра, частоты и нагрева. Лучший алгоритм определяется не названием, а crossover point на целевом устройстве. Сайт - https://2026.hardfest.ru/ Презентация — https://disk.360.yandex.ru/d/d6kakNqs...