Độ phức tạp của thời gian sắp xếp đếm DSA
Xem trang này để biết giải thích chung về độ phức tạp của thời gian.
Đếm độ phức tạp của thời gian sắp xếp
Tính năng Sắp xếp đếm hoạt động bằng cách trước tiên đếm số lần xuất hiện của các giá trị khác nhau, sau đó sử dụng giá trị đó để tạo lại mảng theo thứ tự được sắp xếp.
Theo nguyên tắc chung, thuật toán Sắp xếp Đếm chạy nhanh khi phạm vi giá trị có thể có \(k\) nhỏ hơn số lượng giá trị \(n\).
Để biểu thị độ phức tạp về thời gian bằng ký hiệu Big O, trước tiên chúng ta cần đếm số lượng thao tác mà thuật toán thực hiện:
- Tìm giá trị tối đa: Mỗi giá trị phải được đánh giá một lần để tìm hiểu xem đó có phải là giá trị tối đa hay không, vì vậy cần có các thao tác \(n\).
- Khởi tạo mảng đếm: Với \(k\) là giá trị lớn nhất trong mảng, chúng ta cần các phần tử \(k+1\) trong mảng đếm để bao gồm 0. Mọi phần tử trong mảng đếm phải được khởi tạo, vì vậy \( k+1\) là cần thiết.
- Mọi giá trị chúng ta muốn sắp xếp đều được tính một lần, sau đó bị xóa, do đó, có tổng cộng 2 thao tác cho mỗi lần đếm, tổng cộng là \(2 \cdot n\).
- Xây dựng mảng đã sắp xếp: Tạo các phần tử \(n\) trong mảng đã sắp xếp: các thao tác \(n\).
Tổng cộng chúng tôi nhận được:
\[ \begin{equation} \begin{aligned} Phép toán {} & = n + (k+1) + (2 \cdot n) + n \\ & = 4 \cdot n + k + 1 \\ & \approx 4 \cdot n + k \end{aligned} \end{equation} \]
Dựa trên những gì đã thấy về độ phức tạp thời gian trước đó, chúng ta có thể tạo một biểu thức đơn giản hóa bằng cách sử dụng ký hiệu Big O để biểu thị độ phức tạp thời gian:
\[ \begin{equation} \begin{aligned} O(4 \cdot n + k) {} & = O(4 \cdot n) + O(k) \\ & = O(n) + O(k) \\ & = \underline{\underline{O(n+k)}} \end{aligned} \end{equation} \]
Người ta đã đề cập rằng Sắp xếp đếm có hiệu quả khi phạm vi các giá trị khác nhau \(k\) tương đối nhỏ so với tổng số giá trị được sắp xếp \(n\). Bây giờ chúng ta có thể thấy điều này trực tiếp từ biểu thức Big O \(O(n+k)\).
Ví dụ, chỉ cần tưởng tượng rằng phạm vi của các số khác nhau \(k\) lớn gấp 10 lần số lượng các giá trị cần sắp xếp. Trong trường hợp như vậy, chúng ta có thể thấy rằng thuật toán sử dụng phần lớn thời gian của nó để xử lý phạm vi các số khác nhau \(k\), mặc dù số lượng giá trị thực tế được sắp xếp \(n\) là nhỏ so với.
Sẽ không dễ dàng để hiển thị độ phức tạp về thời gian cho Sắp xếp đếm trong biểu đồ hoặc để mô phỏng độ phức tạp về thời gian như chúng ta đã làm đối với các thuật toán trước đó, vì độ phức tạp về thời gian bị ảnh hưởng rất lớn bởi phạm vi giá trị \( k\).
Dưới đây là biểu đồ cho thấy mức độ phức tạp về thời gian của Sắp xếp đếm có thể khác nhau, theo sau là phần giải thích cho trường hợp tốt nhất và trường hợp xấu nhất.
Trường hợp tốt nhất cho Sắp xếp đếm sẽ là có phạm vi \(k\) chỉ là một phần nhỏ của \(n\), giả sử \(k(n)=0,1 \cdot n\). Ví dụ về điều này, đối với 100 giá trị, phạm vi sẽ là từ 0 đến 10 hoặc đối với 1000 giá trị, phạm vi sẽ là từ 0 đến 100. Trong trường hợp này, chúng ta có độ phức tạp về thời gian \(O(n+k)=O( n+0.1 \cdot n) = O(1.1 \cdot n)\) được đơn giản hóa thành \(O(n)\).
Tuy nhiên, trường hợp xấu nhất sẽ là nếu phạm vi lớn hơn nhiều so với đầu vào. Giả sử đối với đầu vào chỉ có 10 giá trị, phạm vi nằm trong khoảng từ 0 đến 100 hoặc tương tự, đối với đầu vào có 1000 giá trị, phạm vi nằm trong khoảng từ 0 đến 1000000. Trong trường hợp như vậy, mức tăng của \(k\) là bậc hai đối với \(n\), như thế này: \(k(n)=n^2\) và chúng ta nhận được độ phức tạp về thời gian \(O(n+k)=O(n+n^2)\) được đơn giản hóa thành \(O(n^2)\). Một trường hợp thậm chí còn tệ hơn thế này cũng có thể được xây dựng, nhưng trường hợp này được chọn vì nó tương đối dễ hiểu và có lẽ cũng không đến nỗi phi thực tế.
Như bạn có thể thấy, điều quan trọng là phải xem xét phạm vi giá trị so với số lượng giá trị cần sắp xếp trước khi chọn Sắp xếp đếm làm thuật toán của bạn. Ngoài ra, như đã đề cập ở đầu trang, hãy nhớ rằng sắp xếp đếm chỉ hoạt động với các giá trị số nguyên không âm.
Mô phỏng sắp xếp đếm
Chạy các mô phỏng khác nhau của Sắp xếp đếm để xem số lượng thao tác nằm giữa trường hợp xấu nhất \(O(n^2)\) (đường màu đỏ) và trường hợp tốt nhất \(O(n)\) (đường màu xanh lá cây).
{{ this.userX }}
{{ this.userK }}
Hoạt động: {{ hoạt động }}
Như đã đề cập trước đây: nếu các số cần sắp xếp thay đổi nhiều về giá trị (lớn \(k\)) và có ít số cần sắp xếp (nhỏ \(n\)) thì thuật toán Sắp xếp Đếm sẽ không hiệu quả.
Nếu chúng ta giữ cố định \(n\) và \(k\) thì các lựa chọn thay thế "Ngẫu nhiên", "Giảm dần" và "Tăng dần" trong mô phỏng ở trên sẽ dẫn đến cùng một số thao tác. Điều này là do điều tương tự xảy ra trong cả ba trường hợp: Một mảng đếm được thiết lập, các số được đếm và mảng được sắp xếp mới được tạo.
