Độ phức tạp của Radix Sort

Question

Tôi hơi bối rối trước bằng chứng phức tạp của Radix Sort.

Đối với sắp xếp đếm , độ phức tạp được báo cáo là$O(n+R)$, Ở đâu $n$ là số lượng mặt hàng và $R$ là phạm vi.

Nhưng điều này không hoàn toàn chính xác, phải không? Để thực hiện số học nhị phân trên các số lớn như$R$, Tôi cần $\log_2 R$các phép toán cho bất kỳ hàm băm xác định nào. Vì vậy, sự phức tạp của việc đếm shot nên$O(\log_2 R \cdot (n+R))$.

Sau đó, độ phức tạp của sắp xếp cơ số với cơ số$b$ nên là $O(\log_b R \cdot \log_2b \cdot (n+b))$, tương đương với $O(\log_2R \cdot n)$. Đối với phạm vi$R = \Omega(n)$, đây là $\Omega(n \log n)$ và do đó không $O(n)$.

Ai đó có thể chỉ ra chỗ tôi sai trong bằng chứng của tôi không? Theo như tôi biết, sắp xếp cơ số là$O(n)$ cho $R = O(n^c)$.

Answer 1

Chúng tôi thường phân tích các thuật toán trong cái gọi là "máy RAM" hoặc "mô hình transdichotomous". Trong mô hình này, các thao tác trên từ máy sẽ$O(1)$và một từ máy có độ dài $O(\log n)$ bit, ở đâu $n$ là kích thước của đầu vào (tính bằng bit) hoặc bất kỳ đại lượng liên quan đến đa thức nào khác.

Nếu $R$ là đa thức trong $n$ (trong trường hợp này là độ dài của mảng), sau đó là một số nguyên trong phạm vi $\{1,\ldots,R\}$ có thể được lưu trữ trong một từ máy duy nhất và do đó, các hoạt động trên các số nguyên như vậy mất thời gian liên tục trong mô hình này.