Недавно я узнал о сортировке по основанию.
Я знаю, что вы можете изменить базу чисел, которые вам нужно отсортировать, но я действительно не понимаю, почему это хорошо для сортировки по основанию. Время выполнения поразрядной сортировки составляет $O(d(n+k))$, где $d$ — количество цифр в числах, а $k$ — основание.
Так не должно ли быть постоянное соотношение между $d$ и $k$, чтобы оптимизировать время выполнения?
Как я должен выбрать базу по-другому?
Наблюдение, которое, я думаю, вам не хватает, заключается в том, что количество цифр в каждом числе зависит от базы. Например, для числа 255 требуется три цифры по основанию 10 (десятичное), 8 цифр по основанию 2 (двоичное), две цифры по основанию 16 (шестнадцатеричное) и 1 цифра по основанию 256 (я не думаю, что есть название для Это). В более общем случае число n требует (logb n) битов при записи в базе b. Обычно нотация big-O игнорирует основания логарифмов, но, поскольку здесь b — переменная, мы должны принять это во внимание. Используя формулу изменения основания для логарифмов, мы получаем, что нам нужно (log n / log b) бит, чтобы записать число n.
В результате предположим, что вы сортируете список из n чисел, где максимальное число, которое вы сортируете, равно числу U. Если вы выберете основание b, то будет (logb U) = (log U/log b) цифры по основанию b в наибольшем числе, поэтому вам понадобятся (log U/log b) раунды сортировки по основанию. Каждый раунд требует времени (n + b), поэтому общее время выполнения будет ((log U / log b)(n + b)).
Это интересная среда выполнения, поскольку в зависимости от относительных значений n, U и b вы получаете разные результаты. Например, предположим, что вы выбрали b как любое постоянное значение. Тогда это время выполнения равно (n log U), что довольно быстро, но скрытый здесь постоянный фактор имеет большое значение. Если вы используете базу n, где n — количество элементов, то асимптотически время выполнения равно (n log U / log n), что асимптотически быстрее, чем любая фиксированная база, но на практике обычно немного медленнее, за исключением колоссальных входных данных. Если вы знаете, что U будет намного, намного меньше, чем n (скажем, U = o(n), используя нотацию с маленьким o), то вы можете использовать основание U, чтобы получить время выполнения (n), в основном потому, что вы вернуться к стандартной сортировке подсчета здесь.
Как видите, смена базы действительно может иметь большое значение! Я рекомендую поиграть с этим на практике, чтобы увидеть, насколько хорошо теория в конечном итоге работает.
