Độ phức tạp về thời gian sắp xếp hợp nhất DSA
Xem trang này để biết giải thích chung về độ phức tạp của thời gian.
Hợp nhất độ phức tạp của thời gian sắp xếp
Thuật toán Sắp xếp Hợp nhất chia mảng thành các phần nhỏ hơn và nhỏ hơn.
Mảng sẽ được sắp xếp khi các mảng con được hợp nhất lại với nhau để giá trị thấp nhất xuất hiện trước.
Mảng cần được sắp xếp có các giá trị \(n\) và chúng ta có thể tìm thấy độ phức tạp về thời gian bằng cách bắt đầu xem xét số lượng thao tác mà thuật toán cần.
Các hoạt động chính Hợp nhất Sắp xếp thực hiện là phân tách và sau đó hợp nhất bằng cách so sánh các phần tử.
Để phân chia một mảng từ đầu cho đến khi các mảng con chỉ bao gồm một giá trị, Sắp xếp Hợp nhất thực hiện phân chia tổng cộng \(n-1\). Chỉ cần chụp ảnh một mảng có 16 giá trị. Nó được chia một lần thành các mảng con có độ dài 8, được chia đi chia lại nhiều lần và kích thước của các mảng con giảm xuống còn 4, 2 và cuối cùng là 1. Số lần phân chia cho một mảng gồm 16 phần tử là \(1+ 2+4+8=15\).
Hình ảnh bên dưới cho thấy cần phải chia 15 lần cho một mảng gồm 16 số.
Số lần hợp nhất thực tế cũng là \(n-1\), giống như số lần tách, bởi vì mỗi lần tách đều cần một lần hợp nhất để xây dựng mảng lại với nhau. Và đối với mỗi lần hợp nhất, có một sự so sánh giữa các giá trị trong các mảng con để kết quả hợp nhất được sắp xếp.
Trong quá trình hợp nhất hai mảng con, trường hợp xấu nhất tạo ra nhiều sự so sánh nhất là nếu các mảng con có kích thước lớn như nhau. Chỉ cần xem xét việc hợp nhất [1,4,6,9] và [2,3,7,8]. Trong trường hợp này cần có những so sánh sau:
- So sánh 1 và 2, kết quả: [1]
- So sánh 4 và 2, kết quả: [1,2]
- So sánh 4 và 3, kết quả: [1,2,3]
- So sánh 4 và 7, kết quả: [1,2,3,4]
- So sánh 6 và 7, kết quả: [1,2,3,4,6]
- So sánh 9 và 7, kết quả: [1,2,3,4,6,7]
- So sánh 9 và 8, kết quả: [1,2,3,4,6,7,8]
Khi kết thúc quá trình hợp nhất, chỉ còn lại giá trị 9 trong một mảng, mảng còn lại trống, do đó không cần so sánh để đặt giá trị cuối cùng vào và mảng được hợp nhất thu được là [1,2,3,4, 6,7,8,9]. Chúng tôi thấy rằng chúng tôi cần 7 phép so sánh để hợp nhất 8 giá trị (4 giá trị trong mỗi mảng con ban đầu). Nói chung, trong trường hợp xấu nhất, cần phải so sánh \(n-1\) để có được một mảng các giá trị \(n\) được hợp nhất.
Để đơn giản, giả sử chúng ta cần so sánh \(n\) thay vì \(n-1\) khi hợp nhất các giá trị \(n\). Đây là một giả định ổn khi \(n\) lớn và chúng tôi muốn tính giới hạn trên bằng cách sử dụng ký hiệu Big O.
Vì vậy, ở mỗi cấp độ, việc hợp nhất xảy ra, cần có sự so sánh \(n\), nhưng có bao nhiêu cấp độ? Chà, với \(n=16\) chúng ta có \(n=16=2^4\), vậy có 4 cấp độ hợp nhất. Đối với \(n=32=2^5\) có 5 cấp độ hợp nhất và ở mỗi cấp độ, cần có sự so sánh \(n\). Đối với \(n=1024=2^{10}\) cần có 10 cấp độ hợp nhất. Để tìm ra lũy thừa nào của 2 cho 1024, chúng ta sử dụng logarit cơ số 2. Câu trả lời là 10. Về mặt toán học, nó trông như thế này: \( \log_{2}1024=10\).
Như chúng ta có thể thấy trong hình trên, cần có sự so sánh \(n\) ở mỗi cấp độ và có các cấp độ \( \log_{2}n\) nên có \( n \cdot \log_{2}n \) tổng số hoạt động so sánh.
Độ phức tạp về thời gian có thể được tính dựa trên số lượng hoạt động phân tách và số lượng hoạt động hợp nhất:
\[ \begin{equation} \begin{aligned} O( (n-1) + n \cdot \log_{2}n) {} & = O( n \cdot \log_{2}n ) \end{aligned } \end{phương trình} \]
Số lượng thao tác chia \((n-1)\) có thể bị xóa khỏi phép tính Big O ở trên vì \( n \cdot \log_{2}n\) sẽ chiếm ưu thế đối với \( n\) lớn và vì cách chúng tôi tính toán độ phức tạp thời gian cho các thuật toán.
Hình bên dưới cho thấy thời gian tăng lên như thế nào khi chạy Sắp xếp Hợp nhất trên một mảng có giá trị \(n\).
Sự khác biệt giữa trường hợp tốt nhất và trường hợp xấu nhất đối với Sắp xếp Hợp nhất không lớn như đối với nhiều thuật toán sắp xếp khác.
Hợp nhất sắp xếp mô phỏng
Chạy mô phỏng cho số lượng giá trị khác nhau trong một mảng và xem số lượng thao tác Sắp xếp hợp nhất cần trên một mảng các phần tử \(n\) là \(O(n \log n)\):
{{ this.userX }}
Hoạt động: {{ hoạt động }}
Nếu chúng ta giữ số giá trị \(n\) cố định thì số thao tác cần thiết cho "Ngẫu nhiên", "Giảm dần" và "Tăng dần" gần như giống nhau.
Sắp xếp hợp nhất thực hiện gần như giống nhau mọi lúc vì mảng được phân tách và được hợp nhất bằng cách sử dụng so sánh, cả khi mảng đó đã được sắp xếp hay chưa.
