Page 51 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 51
ขั้นตอนว ิธีการค้นหาข้อมูล 15-41
- prev = 7, A[7] = 90 ไม่น้อยกว่า x
- สิ้นส ุดก ารท �ำงาน ของลูป while
- เน่ืองจาก A[7] = x ดังน ั้น ส่งค่ากลับเป็น 7
4. วิเคราะห์ประสทิ ธิภาพของข้ันตอนวธิ ีการคน้ หาข้อมูลแบบกระโดด
การว ิเคราะห์ประสิทธิภาพนั้นจะพ ิจารณาจากลักษณะก ารค้นหาข ้อมูลท ่ีได้ 3 แบบ ดังน้ี
4.1 กรณดี ีทีส่ ดุ
กรณีน ี้ข้อมูลท ี่ต ้องการค้นหาอยู่เป็นสมาชิกตรงค่ากระโดดครั้งแรก เช่น
ข้อมูลท ่ีต้องการค้นหา คือ 16
ข้อมูล 1 7 15 16 23 32 34 35 39 45 56 67 88 89 90 95
n = 16
k = n
= 16
= 4
การค้นหาลักษณะนี้จ ะใช้การเปรียบเทียบแ ค่ครั้งเดียวเสมอดังน ั้น ประสิทธิภาพเชิงเวลาเท่ากับ O(1)
4.2 กรณแี ยท่ ี่สุด
กรณนี ขี้ อ้ มลู ท ต่ี อ้ งการค น้ หาม คี า่ น อ้ ยก วา่ ค า่ ทต่ี ำ� แหนง่ ก ารกร ะโดดค รงั้ ส ดุ ทา้ ย แ ละม ากกวา่ ห รอื เทา่ กบั
ข้อมูลท ่ีต�ำแหน่งก ่อนการกร ะโดดครั้งสุดท้าย
ข้อมูลท่ีต้องการค ้นหา คือ 94
ข้อมูล 1 7 15 16 23 32 34 35 39 45 56 67 88 89 90 95
จ�ำนวนร อบการท�ำซํ้าคือ n โดยห าค ่าม าจากก ารหาอ นุพันธ์ของ f(k) = n/k + (k-1)
ดังนั้นประสิทธิภาพเชิงเวลา = O( n)
4.3 กรณที วั่ ไป
กรณีน ี้ข ้อมูลที่ต ้องการค ้นหามีค ่าอยู่ร ะหว่างก รณีดีท ่ีสุดกับแ ย่ท ี่สุด
ข้อมูลที่ต้องการค้นหา คือ 35
ข้อมูล 1 7 15 16 23 32 34 35 39 45 56 67 88 89 90 95
โดยเฉลี่ยแล้วประสิทธิภาพเชิงเวลาป ระมาณ O( n)
5. การป ระยุกตใ์ ชข้ ้ันตอนวิธีการค้นหาขอ้ มลู แบบกระโดด
ข้ันตอนวิธีแต่ละประเภทโดยทั่วไปแล้วมีงานท่ีเหมาะสมจะประยุกต์ใช้การค้นหาแบบกระโดดเป็นวิธีการที่
เหมาะสมมากส�ำหรับงานท่ีมีจ�ำนวนข้อมูลจ�ำนวนมาก เมื่อเปรียบเทียบกับการค้นหาแบบทวิภาคแล้ว การค้นหาแบบ
ทวภิ าคนน้ั งา่ ยตอ่ การใชแ้ ละประสทิ ธภิ าพโดยรวมคอื O(log (n)) แต่ในกรณขี องจำ� นวนขอ้ มลู มจี ำ� นวนมากการกระโดด
ตรงไปยังต�ำแหน่งกลางอาจเป็นวิธีการที่ไม่เหมาะสมถ้าข้อมูลอยู่ประมาณตอนต้นของล�ำดับรายการ ซ่ึงจะท�ำให้ต้อง
กระโดดย้อนหลังข้ามข้อมูลเป็นจ�ำนวนมาก การใช้งานการค้นหาแบบกระโดดจะมีความเหมาะสมกับงานที่
การเคล่ือนที่ไปข้างหน้ามีความเร็วกว่าเคลื่อนท่ีย้อนหลังทั้งน้ี การค้นหาแบบกระโดดมีการกระโดดย้อนหลังเพียง
ค ร้ังเดียวเท่าน้ัน
