C++ Developer • Cpp System Programming. HighLoad, Алгоритмы и Структуры данных. Разработка на Linux и Windows. STL, Boost, Qt и Embedded.
Прочее · 29 июля 2026 г.
Три теоремы о сортировках — 29 июля 2026 г. в 09:58:21.682
Три теоремы о сортировках Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу? https://habr.com/ru/hubs/cpp/articles/ #cpp #programming 👉 @cpp_lib