Могу ли я отсортировать массив в O (n), если все значения положительные и с цифрами <= k?

Question

Предположим, у меня есть массив A [1 ... n], и нет диапазона для его значений, кроме того, что они положительны. Если я знаю, что они имеют до k цифр, можно ли сортировать массив в O (n)?

Все примеры, с которыми я сталкивался при сортировке O (n), дают верхнюю границу для значений в массиве , Если есть дубликат, пожалуйста, дайте мне знать.

Answer 1

Это зависит от того, является ли k константой или нет.

Если у ваших чисел есть k цифр, то у вас есть ограничение на числа, поскольку они не могут быть больше 10 * 1003. * k - 1. Поэтому вы можете использовать radix sort для сортировки целых чисел. Время выполнения сортировки по основанию - O ((n + b) log _b U), где n - число сортируемых чисел, b - основа вашей сортировки по основанию, а U - максимальное значение, которое ты сортируешь В вашем случае это работает как

O ((n + b) log _b 10 ^k ) = O (k (n + b) ).

Вот тут и появляется «все зависит». Если k - это какое-то фиксированное число, которое никогда не меняется - скажем, всегда 137 или что-то в этом роде - тогда приведенное выше выражение сводится к O ( n + b) и выбор b как любой постоянной (скажем, base-2 для вашей сортировки по основанию) дает время выполнения O (n). С другой стороны, если k может изменяться (скажем, числа могут быть такими большими, как вы хотели бы, чтобы они были, а затем, посмотрев числа, вы определите, что такое k), тогда приведенное выше выражение не может быть упрощенным за пределы O (kn), потому что k является параметром алгоритма.

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

Answer 2

Если k <= n, вы можете, иначе это не гарантируется.

Если я дам вам n = 4 и k = 5, где бы вы разместили элемент 3?