Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Giải Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân - Kết nối tri thức
Luyện tập 2 trang 45 Chuyên đề Tin học 12: Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Lời giải:
Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân (BST) có độ phức tạp thời gian phụ thuộc vào cấu trúc của cây BST trong quá trình chèn và duyệt các phần tử.
Độ phức tạp thời gian của thuật toán sắp xếp bằng BST
1. Chèn phần tử vào BST:
- Trung bình: Đối với cây BST cân bằng, độ sâu trung bình của cây là 
do đó, việc chèn mỗi phần tử có độ phức tạp trung bình là
- Trường hợp xấu nhất: Trong trường hợp xấu nhất, nếu cây BST trở thành một cây một nhánh (giống như danh sách liên kết) khi các phần tử được chèn theo thứ tự tăng hoặc giảm dần, độ sâu của cây sẽ là O(n)O(n)O(n). Vì vậy, việc chèn mỗi phần tử có độ phức tạp là O(n)O(n)O(n).
2. Duyệt cây để lấy các phần tử đã sắp xếp:
- Việc duyệt cây (in-order hoặc reverse in-order) có độ phức tạp là O(n)O(n)O(n) vì chúng ta phải thăm tất cả các nút trong cây một lần.
Tổng độ phức tạp thời gian
- Trung bình: Trong trường hợp trung bình khi cây BST gần như cân bằng, độ phức tạp cho việc chèn n phần tử là 
và duyệt cây là O(n)O(n)O(n). Do đó, tổng độ phức tạp thời gian là
- Trường hợp xấu nhất: Trong trường hợp xấu nhất khi cây BST trở thành một cây một nhánh, độ phức tạp cho việc chèn n phần tử là O(n2)O(n^2)O(n2), và duyệt cây là O(n)O(n)O(n). Do đó, tổng độ phức tạp thời gian là O(n2)O(n^2)O(n2).
Kết luận
- Trung bình:
- Trường hợp xấu nhất: O(n2)O(n^2)O(n2)
Để tránh trường hợp xấu nhất, các thuật toán như AVL tree hoặc Red-Black tree có thể được sử dụng để đảm bảo rằng cây BST luôn gần như cân bằng, giữ độ phức tạp thời gian ở mức
Lời giải bài tập Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân hay, ngắn gọn khác: