TAILIEUCHUNG - Introduction to Algorithms Second Edition Instructor’s Manual 2nd phần 8

Các thuật toán tham lam làm không phải lúc nào cũng mang lại một giải pháp tối ưu. Nhưng đôi khi họ làm. Chúng ta sẽ thấy một vấn đề mà họ làm. Sau đó, chúng tôi sẽ xem xét một số đặc điểm chung của các thuật toán tham lam cho giải pháp tối ưu | 21-2 Lecture Notes for Chapter 21 Data Structures for Disjoint Sets Analysis Since Make-Set counts toward total of operations m n. Can have at most n 1 Union operations since after n 1 Unions only 1 set remains. Assume that the first n operations are Make-Set helpful for analysis usually not really necessary . Application dynamic connected components. For a graph G V E vertices u v are in same connected component if and only if there s a path between them. Connected components partition vertices into equivalence classes. Connected-Components V E for each vertex v e V do Make-Set v for each edge u v e E do if Find-Set u Find-Set v then Union u v Same-Component u v if Find-Set u Find-Set v then return TRUE else return FALSE Note If actually implementing connected components each vertex needs a handle to its object in the disjoint-set data structure each object in the disjoint-set data structure needs a handle to its vertex. Linked list representation Each set is a singly linked list. Each list node has fields for the set member pointer to the representative next List has head pointer to representative and tail. Make-Set create a singleton list. Find-Set return pointer to representative. UNioN a couple of ways to do it. 1. Union x y append x s list onto end of y s list. Use y s tail pointer to find the end. Lecture Notes for Chapter 21 Data Structures for Disjoint Sets 21-3 Need to update the representative pointer for every node on x s list. If appending a large list onto a small list it can take a while. Operation objects updated UNION x1 x2 Union x2 x3 Union x3 x4 UNION x4 x5 1 2 3 4 UNlON xn_1 xn n 1 0 n2 total Amortized time per operation n . 2. Weighted-union heuristic Always append the smaller list to the larger list. A single union can still take Q n time . if both sets have n 2 members. Theorem With weighted union a sequence of m operations on n elements takes O m n lg n time. Sketch of proof Each Make-Set and Find-Set still takes O 1 . How many times can

• Kỹ thuật lập trình
• thủ thuật hệ điều hành
• tìm hiểu hệ điều hành
• thủ thuật windows
• lập trình windows
• lập trình ứng dụng
• lập trình máy tính
• thủ thuật lập trình
• mẹo hay cho lập trình
• bí quyết lập trình
• thủ thuật máy tính
• phần mềm máy tính
• quản trị hệ thống
• hệ điều hành linux
• hệ điều hành mac
• mẹo cài hệ điều hành
• hệ điều hành unix
• hệ điều hành windows
• kỹ năng máy tính
• Hệ Điều Hành
• các hệ điều hành Windows
• giáo trình hệ điều hành
• các vấn đề hệ điều hành
• tài liệu hệ điều hành
• Tổng quan về hệ điều hành
• windows 7
• Refresh hệ điều hành Android
• Hệ điều hành Android cũ
• Hệ điều hành Android
• Cài đặt hệ điều hành Android
• Thủ thuật hệ điều hành Android
• Khôi phục hệ điều hành Android
• đồ họa máy tính
• mỹ thuật đa truyền thông
• học hệ điều hành
• cách sử dụng hệ điều hành
• hệ điều hành windows 7
• mẹo hay hệ điều hành