При каких условиях эти сортировки без сравнения выполняются за линейное время?

Давайте начнем с независимого анализа каждого алгоритма и посмотрим, сможем ли мы определить, в каких случаях они будут выполняться за линейное время.

Во-первых, давайте посмотрим на сортировку подсчетом. Алгоритм работы следующий:

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

Первый шаг можно выполнить за время O(n) путем перебора основного массива. Предположим, что наибольшее значение в массиве равно U. В этом случае второй шаг занимает время O(U), так как нам нужно обнулить элементы массива. Третий шаг занимает время O(n). Затем последний шаг занимает время O(n + U), так как мы посещаем каждый элемент массива частот ровно один раз (O(U)) и делаем в общей сложности n записей в выходной массив O(n). Это означает, что общее время выполнения составляет O(n + U). Обратите внимание, что это зависит как от общего количества элементов, которые необходимо отсортировать (большие массивы требуют больше времени для сортировки), так и от размеров элементов в массиве (большие числа требуют пропорционально большего времени выполнения).

Если мы хотим, чтобы это время выполнения было O (n), нам нужно потребовать, чтобы U = O (n). Таким образом, мы бы получили, что O(n + U) = O(n + n) = O(n). Это означает, что вам нужно, чтобы размер самого большого элемента в массиве рос примерно с той же скоростью, что и длина массива. Например, если вам гарантировано, что все элементы массива находятся в диапазоне 1 .. n, то для завершения сортировки подсчетом потребуется время O(n). Неважно, как эти элементы распределены в этом диапазоне.

По сути, сортировка по основанию работает, многократно выполняя сортировку подсчетом снова и снова, по одному разу для каждой цифры чисел в сортируемом массиве. Ключевая идея сортировки по основанию состоит в том, чтобы сохранить значение U из предыдущего алгоритма как можно ниже. Выбирая некоторую фиксированную базу, значение U ограничивается некоторой константой. Например, если вы используете двоичную сортировку по основанию и переходите по одному биту за раз, каждый элемент массива для сортировки, по сути, обрабатывается либо как 0, либо как 1. Это означает, что каждый раунд сортировки по основанию занимает время O( н) завершить. Затем количество раундов, необходимое для сортировки всего массива, определяется количеством цифр в наибольшем числе в массиве, которое равно (log U). Это означает, что общее время выполнения алгоритма составляет O(n log U). Еще раз обратите внимание, что время выполнения зависит от количества элементов и размера самого большого элемента в массиве.

Преимущество на этот раз в том, что log U растет намного, гораздо медленнее, чем U. Например, 2³⁰⁰ соответствует общему числу атомов во Вселенной, а lg (2^{300) = 300, что совсем немного.}

Некоторые люди будут утверждать, что журнал U является константой на любом стационарном компьютере. На 32-разрядном компьютере все целые числа являются 32-разрядными (если только вы не используете библиотеки целых чисел произвольной точности, которые мы пока проигнорируем), а в 64-разрядной системе все целые числа являются 64-разрядными. В первом случае log U = 32, а во втором log U = 64. Можно утверждать, что для фиксированной системы поразрядная сортировка всегда занимает линейное время, поскольку время выполнения будет O(n ). Однако константа варьируется от системы к системе. Если вы более теоретически настроены и хотите быть более точным, вы можете сказать, что сортировка по основанию выполняется за линейное время, пока log U = O (1), поскольку таким образом O (n log U) = O (n). Это означает, что если у вас есть какая-либо постоянная верхняя граница количества битов в числе, вам гарантировано, что сортировка по основанию будет выполняться за линейное время.

Алгоритм групповой сортировки аналогичен сортировке по основанию, за исключением того, что он распределяет элементы по старшему, а не по младшему разряду. Это означает, что анализ почти такой же, как и раньше — пока log U = O(1), алгоритм работает за линейное время.

Надеюсь это поможет!