Độ phức tạp thời gian DSA cho các thuật toán cụ thể

Xem trang này để biết giải thích chung về độ phức tạp của thời gian.

Độ phức tạp của thời gian Quicksort

Thuật toán Quicksort chọn một giá trị làm phần tử 'trục' và di chuyển các giá trị khác sao cho các giá trị cao hơn ở bên phải phần tử trục và các giá trị thấp hơn nằm ở bên trái của phần tử trục.

Sau đó, thuật toán Quicksort tiếp tục sắp xếp đệ quy các mảng con ở bên trái và bên phải của phần tử trục cho đến khi mảng được sắp xếp.

Trường hợp xấu nhất

Để tìm độ phức tạp về thời gian của Quicksort, chúng ta có thể bắt đầu bằng cách xem xét trường hợp xấu nhất.

Trường hợp xấu nhất đối với Quicksort là nếu mảng đã được sắp xếp. Trong trường hợp như vậy, chỉ có một mảng con sau mỗi lệnh gọi đệ quy và các mảng con mới chỉ ngắn hơn một phần tử so với mảng trước đó.

Điều này có nghĩa là Quicksort phải gọi chính nó theo cách đệ quy \(n\) lần và mỗi lần nó phải thực hiện các phép so sánh \(\frac{n}{2}\) trung bình.

Độ phức tạp về thời gian trong trường hợp xấu nhất là:

\[ O(n \cdot \frac{n}{2}) = \underline{\underline{O(n^2)}} \]

Trường hợp trung bình

Trung bình, Quicksort thực sự nhanh hơn nhiều.

Quicksort trung bình nhanh vì mảng được chia đôi khoảng một nửa mỗi lần Quicksort chạy đệ quy và do đó kích thước của các mảng phụ giảm rất nhanh, điều đó có nghĩa là không cần nhiều lệnh gọi đệ quy và Quicksort có thể kết thúc sớm hơn trong tình huống xấu nhất.

Hình ảnh bên dưới cho thấy cách chia một mảng gồm 23 giá trị thành các mảng con khi được sắp xếp bằng Quicksort.

Phần tử trục (màu xanh lá cây) được di chuyển vào giữa và mảng được chia thành các mảng con (màu vàng). Có 5 cấp độ đệ quy với các mảng con ngày càng nhỏ hơn, trong đó khoảng giá trị \(n\) được chạm vào bằng cách nào đó ở mỗi cấp độ: được so sánh, hoặc di chuyển hoặc cả hai.

\( \log_2 \) cho chúng ta biết một số có thể chia làm 2 bao nhiêu lần, vì vậy \( \log_2 \) là một ước tính tốt về số lượng cấp độ đệ quy. \( \log_2(23) \approx 4.5 \) là một xấp xỉ đủ tốt về số lượng cấp độ đệ quy trong ví dụ cụ thể ở trên.

Trong thực tế, các mảng con không được chia chính xác làm đôi mỗi lần và không có giá trị \(n\) chính xác nào được so sánh hoặc di chuyển ở mỗi cấp độ, nhưng chúng ta có thể nói rằng đây là trường hợp trung bình để tìm độ phức tạp về thời gian:

\[ \underline{\underline{O(n \cdot \log_2n)}} \]

Dưới đây, bạn có thể thấy sự cải thiện đáng kể về độ phức tạp về thời gian của Quicksort trong trường hợp trung bình, so với các thuật toán sắp xếp trước đó Sắp xếp bong bóng, lựa chọn và chèn:

Phần đệ quy của thuật toán Quicksort thực sự là lý do tại sao kịch bản sắp xếp trung bình lại nhanh như vậy, bởi vì để chọn tốt phần tử trục, mảng sẽ được chia đôi một cách đồng đều mỗi khi thuật toán gọi chính nó. Vì vậy số lượng lệnh gọi đệ quy không tăng gấp đôi, ngay cả khi số lượng giá trị \(n \) tăng gấp đôi.

Mô phỏng sắp xếp nhanh

Sử dụng mô phỏng bên dưới để so sánh độ phức tạp về thời gian theo lý thuyết \(O(n^2)\) (đường màu đỏ) với số lượng thao tác của các lần chạy Quicksort thực tế.

Đường màu đỏ ở trên biểu thị độ phức tạp thời gian giới hạn trên theo lý thuyết \(O(n^2)\) cho trường hợp xấu nhất và đường màu xanh lá cây biểu thị độ phức tạp thời gian của kịch bản trong trường hợp trung bình với các giá trị ngẫu nhiên \(O(n \log_2n)\ ).

Đối với Quicksort, có sự khác biệt lớn giữa các trường hợp ngẫu nhiên trung bình và các trường hợp trong đó mảng đã được sắp xếp. Bạn có thể thấy điều đó bằng cách chạy các mô phỏng khác nhau ở trên.

Lý do tại sao mảng đã được sắp xếp tăng dần lại cần nhiều thao tác như vậy là vì nó yêu cầu hoán đổi các phần tử nhiều nhất do cách nó được triển khai. Trong trường hợp này, phần tử cuối cùng được chọn làm phần tử trụ và phần tử cuối cùng cũng là số cao nhất. Vì vậy, tất cả các giá trị khác trong mỗi mảng con được hoán đổi xung quanh để nằm ở phía bên trái của phần tử trục (nơi chúng đã được định vị).