tailieunhanh - Ebook Giáo trình thuật toán: Phần 2 - NXB Thống kê

Phần 2 ebook gồm các nội dung chính: Các cấu trúc dữ liệu cao cấp, thuật toán đồ thị, các chủ đề chọn lọc. chi tiết nội dung tài liệu. | V Các Cấu Trúc Dữ Liệu Cao cấp Mở đầu Phần này quay lại việc xem xét các cấu trúc dữ liệu hỗ trợ các phép toán trến các tập hợp động nhưng ở một cấp cao hơn so với Phần III. Ví dụ hai trong số các chương vận dụng rộng rãi các kỹ thuật phân tích khâu trừ mà ta đã gặp trong Chương 18. Chương 19 trình bày các cây B là các cây tìm kiếm cân đối được thiết kế để lưu trữ trên các đĩa từ. Bởi các đĩa từ vận hành chậm hơn nhiều so với bộ nhớ truy cập ngẫu nhiến ta đo khả năng thực hiện của các cây B không những bằng quãng thời gian tính toán mà các phép toấn tập hợp động tiêu thụ mà còn bằng số lần truy cập đìa được thực hiện. Với mỗi phép toán cây B số lần truy cập đĩa gia tăng theo chiều cao của cây B được các phép toán cây B duy trì ở mức tháp. Các chương 20 và 21 đề cập các cách thực thi các đống khả trộn mergeable heaps hổ trỢ các phép toấn INSERT MINIMUM. EX-TRACT-MIN và UNION. Phép toan UNION hợp nhát hoặc trộn hai đống. Các cấu trúc dữ liệu trong các chương này cũng hỗ trỢ các phép toán DELETE và DECREASE-KEY. Các đống nhị thức xuất hiện trong Chương 20 hỗ trợ lừng phép toán này trong ơ lg n thời gian trường hợp xấu nhất ở đó n là tổng các thành phẩn trong đông nhập liệu hoậc trong hai đống nhập liệu với nhau trong trường hỢp UNION . Khi phép toán UNION phai được hỗ trợ thì chính là lúc các đống nhị thức tỏ ra vượt trội so với các đông nhị phân đã giới thiệu trong Chương 7 bởi nó mất 0 n thời gian để hợp nhất hai đống nhị phân trong trường hợp xâ u nha t. Các đống Fibonacci trong Chương 21 vượt trội hơn các đống nhị thức ít nhât theo nghĩa lý thuyêt. Ta dùng cấc cận thời gian khấu trừ để đo khả năng thực hiện của cấc đống Fibonacci. Các phép toán INSERT MINIMUM và UNION chỉ mât 0 1 thời gian thực tê và khâu trừ trên các đống Fibonacci và các phép toán EXTRACT-M1N và DELETE mất ỡ lg n thời gian khấu trừ. Tuy nhiên ưu điểm quan trọng nhất của các đống Fibonacci đó là DECREASE-KEY chỉ mất O I thời gian khấu trừ. Thời gian khấu trừ thấp của phép toán DECREASE-KEY chính