Radix Sort - O(n) Time

Question

Я слышал, что если мы сортируем n числа и что сортируемые числа были преобразованы в основание n, тогда радикальная сортировка могла быть выполнена за O(n) время.

Я правильно понял?

Если да, то как именно это достигается. Если мы имеем дело с 5 числами и преобразуем их все в основание 5, мы можем разделить цифры на 5 сегментов (0, 1, 2, 3, 4).

Даже если бы числа, с которыми мы имели дело, имели максимум 7 цифр, разве вам не пришлось бы циклически проходить по крайней мере 7 * 5 раз? Это не кажется правильным... однако.

Извините, вроде запутался по этому поводу.

Спасибо за вашу помощь.

Answer 1

Radix sort работает путем выбора некоторой числовой базы b, записи всех чисел на входе в base b, а затем сортировки чисел по одной цифре за раз. В этом ответе я сосредоточусь на сортировке по осям наименьших значащих цифр, в которой мы сортируем все по наименьшим значащим цифрам, затем вторым младшим значащим цифрам и т. Д.

Каждый раз, когда мы сортируем числа по некоторой цифре, мы должны выполнить O(n) работу, чтобы распределить элементы по всем сегментам, затем O(n + b) выполнить итерацию по сегментам и получить элементы в отсортированном порядке. Следовательно, время выполнения для одного раунда сортировки по основанию равно O(n + b).

Количество раундов радикальной сортировки зависит от количества цифр в каждом из чисел. Если вы напишите числа в базе b, в числе M будет O (log_b M) цифр base-b. Если мы допустим, чтобы M обозначало максимальное число во входном массиве, то число раундов сортировки по основанию будет тогда O (журнал_б М). Следовательно, асимптотическое время выполнения радикальной сортировки

O(n + b) · O (log_b M) = O ((n + b) log_b M).

В типичной двоичной радикальной сортировке вы выбрали бы b = 2 и получили бы время выполнения O(n log M). Тем не менее, вы можете выбрать b для любого значения, которое вы хотите. Если вы выберете большее значение b, то будет меньше цифр base-b в каждом из чисел (например, напишите число в base-10, а затем в base-16; вам обычно нужно меньше цифр в база-16). В вашем оригинальном вопросе вы спросили

Даже если бы числа, с которыми мы имели дело, имели максимум 7 цифр, разве вам не пришлось бы циклически проходить по крайней мере 7 * 5 раз?

Ответ "не обязательно". Если вы выполните основную 10-кратную сортировку с 7-значными числами, то да, вам придется повторить цикл 7 раз. Однако, если вы использовали сортировку по основанию 100, вам нужно было бы выполнить цикл только 4 раза.

Ваш другой вопрос был об использовании base-n для сортировки по основанию. Если мы выберем основание, которое мы используем, как число n, то получим, что время выполнения

O ((n + n) log_n M) = O (n log_n M) = O (n log M / log n)

(При этом используется формула изменения базиса для логарифмов для перезаписи log_n M = log M / log n).

Это не O(n), и вы не должны этого ожидать. Подумайте об этом так: время выполнения радикальной сортировки зависит от длины сортируемых строк. Если вы сортируете небольшое количество чрезвычайно длинных чисел, время выполнения должно быть больше, чем время сортировки небольшого числа маленьких чисел просто потому, что вам действительно нужно прочитать цифры большого числа. Хитрость использования base n - это просто метод асимптотического ускорения алгоритма.

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