Sidebar
dsa:dsintro
8. THE DISJOINT SET ADT
ในบทนี้กล่าวถึงโครงสร้างข้อมูลที่ใช้ในการแก้ปัญหาที่เรียกว่า ปัญหาการสมมูล (equivalence problem) เป็นโครงสร้างข้อมูลที่ง่ายในการสร้าง โปรแกรมที่เขียนสำหรับโครงสร้างนี้มีขนาดเล็ก สามารถใช้โครงสร้างแบบอะเรย์ได้ และสามารถทำงานได้อย่างรวดเร็วใช้เวลาเฉลี่ยเป็นเวลาคงที่ต่อการทำงานหนึ่ง โครงสร้างข้อมูลชนิดนี้เป็นที่สนใจในทางทฤษฏีเนื่องจากการวิเคราะห์ทำได้ยากมากรูปแบบฟังก์ชันของกรณี worst case ก็แตกต่างจากที่ได้ที่ได้กล่าวมาแล้ว เนื้อหาที่จะกล่าวเกี่ยวกับ Disjoint set ADT:
- แสดงการ implement ประกอบด้วยคำสั่งสั้น ๆ
- วิเคราะห์ running time
- ตัวอย่างการประยุกต์ใช้งานอย่างง่าย
dsa/dsintro.txt · Last modified: 2021/09/08 13:24 by wasu
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
