Złożoność sortowania Radix

Question

Jestem trochę zdezorientowany dowodem złożoności Radix Sort.

W przypadku sortowania zliczania zgłaszana złożoność wynosi$O(n+R)$, gdzie $n$ to liczba elementów i $R$ jest zasięgiem.

Ale to nie jest do końca poprawne, prawda? Wykonywanie arytmetyki binarnej na liczbach tak dużych jak$R$, Potrzebuję $\log_2 R$operacje dla dowolnej deterministycznej funkcji mieszającej. Więc złożoność liczenia strzałów powinna być$O(\log_2 R \cdot (n+R))$.

Następnie złożoność sortowania radix z podstawą$b$ Powinien być $O(\log_b R \cdot \log_2b \cdot (n+b))$, co jest równoważne z $O(\log_2R \cdot n)$. Zasięg$R = \Omega(n)$, to jest $\Omega(n \log n)$ a więc nie $O(n)$.

Czy ktoś może wskazać, gdzie popełniam błąd w swoim dowodzie? O ile wiem, sortowanie radix to$O(n)$ dla $R = O(n^c)$.

Answer 1

Zazwyczaj analizujemy algorytmy w tzw. „Maszynie RAM” lub „modelu transdychotomicznym”. W tym modelu są wykonywane operacje na słowach maszynowych$O(1)$, a słowo maszynowe ma długość $O(\log n)$ bity, gdzie $n$ jest rozmiarem wejścia (w bitach) lub dowolną inną wielkością wielomianową.

Gdyby $R$ jest wielomianem w $n$ (w tym przypadku długość tablicy), a następnie liczbę całkowitą z zakresu $\{1,\ldots,R\}$ mogą być przechowywane w jednym słowie maszynowym, więc operacje na takich liczbach całkowitych trwają w tym modelu przez stały czas.