Сложность Radix Sort

Question

Меня немного смущает доказательство сложности Radix Sort.

Для подсчета сортировки сообщаемая сложность составляет$O(n+R)$, где $n$ это количество предметов и $R$ это диапазон.

Но это не совсем так, правда? Чтобы выполнять двоичную арифметику с числами размером$R$, Я нуждаюсь $\log_2 R$операции для любой детерминированной хеш-функции. Так что сложность подсчета выстрелов должна быть$O(\log_2 R \cdot (n+R))$.

Тогда сложность поразрядной сортировки с базой$b$ должно быть $O(\log_b R \cdot \log_2b \cdot (n+b))$, что эквивалентно $O(\log_2R \cdot n)$. Для диапазона$R = \Omega(n)$, это $\Omega(n \log n)$ и поэтому не $O(n)$.

Может ли кто-нибудь указать, где я ошибаюсь в доказательстве? Насколько мне известно, поразрядная сортировка$O(n)$ для $R = O(n^c)$.

Answer 1

Обычно мы анализируем алгоритмы в так называемой «RAM-машине» или «трансдихотомической модели». В этой модели операции над машинными словами принимают$O(1)$, а машинное слово имеет длину $O(\log n)$ биты, где $n$ - это размер входных данных (в битах) или любая другая полиномиально связанная величина.

Если $R$ полиномиален от $n$ (в данном случае длина массива), затем целое число в диапазоне $\{1,\ldots,R\}$ могут быть сохранены в одном машинном слове, и поэтому операции с такими целыми числами в этой модели занимают постоянное время.