TAILIEUCHUNG - Chuyên đề cấu trúc dữ liệu đặc biệt

Trong chuyên đề này ta sẽ nhắc tới 2 loại cấu trúc đặc biệt , đó là Interval Tree và Binary Index Tree. Đó là 2 cách tổ chức dữ liệu rất thông minh , việc tổ chức này cũng dẫn tới việc tìm ra những thuật toán hay với cấp độ trung bình thấp O(NlogN) . Và để trình bày ý tưởng của các thuật toán này ta sẽ xem xét nó thông qua các bài toán cụ thể để có thể hiểu rõ hơn. | Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu CHUYÊN ĐỀ CẤU TRÚC DỮ LIỆU ĐẶC BIỆT A . Lý thuyết Trong chuyên đề này ta sẽ nhắc tới 2 loại cấu trúc đặc biệt đó là Interval Tree và Binary Index Tree. Đó là 2 cách tổ chức dữ liệu rất thông minh việc tổ chức này cũng dẫn tới việc tìm ra những thuật toán hay với cấp độ trung bình thấp O NlogN . Và để trình bày ý tưởng của các thuật toán này ta sẽ xem xét nó thông qua các bài toán cụ thể để có thể hiểu rõ hơn. I . Interval Tree Bài toán Cho N hình chữ nhật trong mặt phẳng toạ độ. Hãy tính diện tích bị phủ bởi N hình chữ nhật này. Giới hạn 1 N 2000. Các toạ độ đều là số nguyên . Time limit s bộ nhớ 200 KB. Phân tích Đối với bài toán này ta có thể giải bằng giải thuật thông thường với cấp độ O N2 . Đó là sắp xếp các hình chữ nhật theo toạ độ Y sau đó tính diện tích bị phủ giữa 2 khe. Tổng diện tích bị phủ sẽ là tổng diện tích bị phủ giữa 2 khe . C1 C2 C3 C4 C5 C6 C7 C8 B1 B2 B3 B4 B5 B6 B7 B8 Hình 1 Ở hình 1 ta thấy có các khe B1B2 B2B3 . B7B8. Vì đã sắp xếp các HCN tăng dần theo tung độ nên với mỗi khe ta chỉ cần thao tác đơn giản là xét từ 1 - N những HCN nào phủ lên khe đó mà thôi. Có tất cả khoảng N 2 - 1 khe với mỗi khe ta xét N HCN - Cấp độ chính xác O 2 N2 . Rõ ràng với N 2000 thì trong vòng s chương trình khó có thể trả ra kết quả ngay được. Trang 1 Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu Chắc hẳn rất nhiều bạn cũng sẽ nghĩ ra thuật toán này và có thể sẽ băn khoăn một điều rằng liệu có cách gì để chỉ xét mỗi hình chữ nhật đúng một lần hay không Cấu trả lời là nếu muốn chỉ xét 1 lần thì hiện thời mình cũng không biết nhưng mà mình biết có thuật toán có thể đáp ứng yêu cầu với số lần xét là 2 lần Nội dung thuật toán và cách làm Nếu như ở thuật toán O N2 ta chỉ xét các khe theo hoành độ các khe B thì ở đây ta lại quan tâm tới khe theo tung độ các khe C . Tuy nhiên về mặt bản chất thuật toán vẫn không có gì thay đổi vẫn chỉ là tính diện tích giữa các khe hoành độ mà thôi. Ta sẽ phân tách

• Kỹ thuật lập trình
• Thuật toán
• cấu trúc dữ liệu đặc biệt
• Interval tree
• Binary Index Tree
• cách tổ chức dữ liệu
• Thuật toán và tư duy thuật toán
• Đặc trưng cơ bản về thuật toán
• Thiết kế thuật toán
• Hiệu quả giảng dạy thuật toán
• Cài đặt thuật toán
• Vấn đề tư duy thuật toán
• Ngôn ngữ lập trình
• Bài giảng thuật toán
• Biểu diễn thuật toán
• Kỹ thuật thiết kế thuật toán
• Phân tích thuật toán
• Đáng giá thuật toán
• Thuật toán máy tính
• Thuật toán tham lam
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Tự học lập trình
• Bài giảng Tin học 10
• Bài giảng Tin học 10 Bài 4
• Bài 4 Bài toán và thuật toán
• Bài giảng Bài toán và thuật toán
• Khái niệm bài toán
• Khái niệm thuật toán
• Thuật toán tìm Max của một dãy số
• Cẩm nang thuật toán
• Phương pháp giải thuật toán
• Thuật toán thông dụng
• Thuật toán sắp xếp
• Thuật toán tìm kiếm
• Thuật toán xử lý chuỗi
• Thuật toán chuyên dụng
• Một số vấn đề về thuật toán
• Độ phức tạp thuật toán
• Phương pháp trong thuật toán
• Tính đúng đắn của thuật toán
• thuật toán DDA
• thuật toán bresenham
• thuật toán đường tròn
• thuật toán MidPoint
• thuật toán vẽ Ellipse
• Thuật toán tô màu
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Thuật toán Google
• Thuật toán Sand
• Thuật toán chim ruồi
• Thuật toán ngựa vằn Zebra Box
• Thuật toán Chim cánh cụt
• Thuật toán Gấu trúc Panda
• Đề thi cuối kì môn Toán kỹ thuật
• Bài thi môn Toán kỹ thuật
• Ôn thi Toán kỹ thuật
• Luyện thi Toán kỹ thuật
• Tài liệu thi Toán kỹ thuật
• Hướng dẫn thi Toán kỹ thuật
• Lý thuyết thuật toán tìm đường
• Thuật toán tìm đường
• Thuật toán tìm đường đi ngắn nhất
• Thuật toán tìm đường đi
• Xây dựng thuật toán
• Thuật toán xử lý thông tin
• Đặc trưng của thuật toán
• Thuật toán Euclid cải tiến
• Ngôn ngữ thuật toán
• Diễn tả thuật toán
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Trình diễn thuật toán
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Tính chất của thuật toán
• Đặc tả thuật toán
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Quy hoạch động
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Khóa luận tốt nghiệp
• Khóa luận tốt nghiệp Kế toán Kiểm toán
• Kế toán Kiểm toán
• Kế toán thanh toán
• Nguyên tắc kế toán thanh toán với người mua
• Nguyên tắc kế toán thanh toán với người bán
• Thuật toán gần đúng
• Bài toán tối ưu tổ hợp
• Tối ưu tổ hợp
• Toán tối ưu tổ hợp
• Ứng dụng thuật toán gần đúng
• Tìm hiểu thuật toán gần đúng
• Tài liệu thuật toán gần đúng
• Sáng kiến kinh nghiệm
• Bài tập xây dựng thuật toán giải bài toán
• Thuật toán giải bài toán
• Xây dựng thuật toán máy tính
• Kỹ thuật kiểm toán
• tài liệu Kỹ thuật kiểm toán
• bài giảng Kỹ thuật kiểm toán
• kế toán kiểm toán
• nghiệp vụ kế toán
• kế toán tài chính
• kế toán doanh nghiệp