Độ phức tạp sắp xếp hợp nhất được tính như thế nào?

2024 Tác giả: Lynn Donovan | [email protected]. Sửa đổi lần cuối: 2023-12-15 23:55

2 Câu trả lời. Việc tách một nút A [L, R] thành hai nút mất R − L + 1 lần và sau đó hợp nhất hai nút con A [L, M] và A [M + 1, R] lại mất A [R − L + 1] thời gian. Vì vậy, đối với mọi nút, số lượng hoạt động thuật toán Thực hiện bằng hai lần kích thước của mảng tương ứng với nút đó.

Về điều này, sắp xếp hợp nhất hoạt động như thế nào?

Dưới đây là cách sắp xếp hợp nhất sử dụng phân chia và chinh phục:

1. Chia cho việc tìm số q của vị trí giữa p và r.
2. Chinh phục bằng cách sắp xếp đệ quy các mảng con trong mỗi bài toán con trong hai bài toán con được tạo bởi bước chia.
3. Kết hợp bằng cách hợp nhất hai mảng con đã sắp xếp trở lại thành mảng mảng con được sắp xếp duy nhất [p.

Ngoài ra, độ phức tạp O lớn đối với sắp xếp hợp nhất là gì? Hợp nhất Sắp xếp là một chuồng loại có nghĩa là cùng một phần tử trong một mảng duy trì vị trí ban đầu của chúng đối với nhau. Tổng thời gian phức tạp của Hợp nhất sắp xếp Là O (nLogn). Nó hiệu quả hơn vì trong trường hợp xấu nhất, thời gian chạy cũng O (nlogn) Khoảng trống phức tạp của Hợp nhất sắp xếp Là O (n).

độ phức tạp của sắp xếp hợp nhất trong trường hợp xấu nhất là gì?

n * log (n)

Sắp xếp hợp nhất thực hiện bao nhiêu so sánh?

Khi chúng tôi sử dụng hết các phần tử trong một trong các danh sách, chúng tôi đặt các phần tử còn lại vào các vị trí cuối cùng của đã sắp xếp danh sách. Kết quả là, hợp nhất hai danh sách có tổng số n phần tử yêu cầu nhiều nhất n-1 sự so sánh.