Page 12 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 12
15-2 โครงสร้างข ้อมูลและขั้นต อนว ิธี
แผนการสอนป ระจ�ำ ห นว่ ย
ชดุ วชิ า โครงสร้างข้อมูลและขั้นต อนวิธี
หน่วยที่ 15 ข้ันตอนว ิธีก ารค้นหาข้อมูล
ตอนท ่ี
15.1 การค ้นหาข ้อมูลพื้นฐ าน
15.2 การค ้นหาข ้อมูลแ บบอ ื่น
แนวคิด
1. การค้นหาข้อมูลหมายถึง การดึงข้อมูลท่ีต้องการจากโครงสร้างข้อมูลท่ีใช้ในการจัดเก็บข้อมูลหรือจาก
ฐานข้อมูล สามารถแ บ่งได้เป็น 2 ประเภทข้ึนอยู่กับโครงสร้างการจัดเก็บข ้อมูลได้แก่ การค้นหาข้อมูลบน
โครงสร้างก ารจ ัดเก็บเชิงเส้น และการค้นหาข ้อมูลบนโครงสร้างการจ ัดเก็บไม่เชิงเส้น วิธีการค ้นหาข้อมูล
พื้นฐ านคือวิธีก ารแ บบบ รูทฟอ ร์ซซ่ึงเปรียบเทียบข ้อมูลท ีล ะต�ำแหน่งเรียงก ันไป เริ่มจ ากต �ำแหน่งแ รกถ ึง
ต�ำแหน่งสุดท้าย ซ่ึงวิธีการนี้ข้อมูลไม่จ�ำเป็นต้องมีการจัดเรียงมาก่อน ส่วนวิธีการค้นหาข้อมูลแบบ
เรียงล �ำดับใช้ก ับข ้อมูลท ี่มีการเรียงล �ำดับม าแ ล้วซึ่งเทคนิคก ารค ้นหาน ั้นจะค ล้ายก ับว ิธีการข อง บร ูทฟ อร์ซ
2. วิธีการค้นหาข้อมูลที่สลับซับซ้อนและมีประสิทธิภาพมากขึ้น ได้แก่วิธีการแบบทวิภาค แบบกระโดด
แบบการประมาณค่าในช่วง และแบบฟิโบนักซี ซ่ึงไม่ใช้การเปรียบเทียบทีละต�ำแหน่งเรียงกันไป แต่ใช้
การตรวจสอบเปน็ ชว่ งๆ ซงึ่ ระยะของชว่ งนน้ั มคี วามแตกตา่ งกนั ไปขน้ึ อยกู่ บั ขนั้ ตอนวธิ นี นั้ ๆ การตรวจสอบ
เป็นช่วงท�ำให้ลดระยะเวลาการตรวจสอบซ่ึงท�ำให้ประสิทธิภาพเชิงเวลาดีกว่าการค้นหาแบบบรูทฟอร์ซ
และแ บบเรียงล �ำดับ
วตั ถปุ ระสงค์
เมื่อศ ึกษาห น่วยท ่ี 15 จบแ ล้ว นักศึกษาสามารถ
1. อธิบายหลักก าร แนวคิด และป ระเภทข องก ารค ้นหาข ้อมูลได้
2. อธิบายหลักการของการค้นหาข้อมูลแบบบรูทฟอร์ซ แบบเรียงล�ำดับ แบบทวิภาค แบบกระโดด
แบบก ารป ระมาณค่าในช ่วง และแบบฟ ิโบนักซ ีได้
3. อธบิ ายแ ละแ สดงข นั้ ต อนว ธิ ขี องก ารค น้ หาข อ้ มลู แ บบบ รทู ฟอ รซ์ แบบเรยี งล ำ� ดบั แบบท วภิ าค แบบก ระโดด
แบบการประมาณค ่าในช ่วง และแบบฟิโบนักซีได้
4. ประยุกต์ใช้ขั้นตอนวิธีการค้นหาข้อมูลแบบบรูทฟอร์ซ แบบเรียงล�ำดับ แบบทวิภาค แบบกระโดด
แบบก ารป ระมาณค ่าในช่วง และแบบฟ ิโบนักซีได้
