Page 65 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 65
ขั้นต อนว ิธีการค้นหาข ้อมูล 15-55
รอบท ่ี 2
index = 5 (index = first + f1 = 0 + 5)
5 9 13 17 24 29 34 38 42 53
index = 5
f2 = 3 f1 = 5
บรรทัดท ี่ 18 เงื่อนไข index >= n (5 >= 10) ไม่จริง
x < A[index] (24 < 24) ไม่จ ริง
บรรทัดที่ 24 เงื่อนไข x = A[ index] (24 = 24) จริง
บรรทัดที่ 25 ส่งค ่าก ลับเป็น 5
4. วิเคราะห์ประสทิ ธิภาพของข ั้นตอนว ธิ ีการค้นหาขอ้ มูลแบบฟิโบนักซี
การว ิเคราะห์ป ระสิทธิภาพน ้ันจะพ ิจารณาจ ากล ักษณะการค ้นหาข้อมูลท่ีได้ 3 แบบ ดังน้ี
4.1 กรณีดที ส่ี ดุ
กรณีน ้ีข้อมูลม ีก ารเรียงต ัวเพิ่มข ึ้นเป็นเชิงเส้น และค่าข องข้อมูลม ีก ารกระจ ายต ัวท่ีด ี เช่น
ข้อมูลที่ต ้องการค ้นหา คือ 24
ข้อมูล 5 9 13 17 24 29 34 38 42 53
การค้นหาลักษณะน ี้จะม ีป ระสิทธิภาพเชิงเวลาเท่ากับ O(log n))
4.2 กรณแี ย่ที่สดุ
กรณีน ้ีข้อมูลมีก ารเรียงล�ำดับโดยค่าท่ีเพ่ิมข้ึนม ีการกระจายตัวท่ีไม่ดี เช่น
ข้อมูลท่ีต ้องการค้นหา คือ 100
ข้อมูล 5 8 9 13 100 1000
ประสิทธิภาพเชิงเวลา = O(n)
4.3 กรณีทั่วไป
กรณีท ั่วไปข องก ารค ้นหาข ้อมูลจ ากข ้อมูลท ี่เรียงล �ำดับแ ล้วด ้วยว ิธีการค ้นหาแ บบฟิโบนักซีจะเหมือนก ับ
กรณีดีท่ีสุด คือ ข้อมูลมีการเพิ่มขึ้นแบบเชิงเส้นและค่าของข้อมูลมีการกระจายตัวท่ีดี ซึ่งประสิทธิภาพเชิงเวลาคือ
O(log n))
5. การป ระยกุ ตใ์ ช้ขนั้ ตอนว ธิ กี ารคน้ หาขอ้ มลู แบบฟโิ บนักซี
ข้ัน ต อน วิธีแต่ละประเภทโดยท่ัวไปแล้วมีงานท่ีเหมาะสมจะประยุกต์ใช้ การค้นหาแบบ Fibonacci
เหมาะสมกับข้อมูลที่มีการกระจายตัวมาก ข้อมูลใช้เวลาในการเข้าถึงไม่เป็นแบบเดียวกัน เช่นการเข้าถึงข้อมูลคร้ัง
ต่อไปข้ึนอยู่กับการเข้าถึงข้อมูลก่อนหน้านี้ ตัวอย่างความเหมาะสมการใช้งาน เช่น การค้นหาจากอาร์เรย์ขนาดใหญ่
ที่ไม่สามารถจัดเก็บได้ทั้งหมดในแคชข องซ ีพียู หรือหน่วยความจ �ำหลัก เป็นต้น
