Page 58 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 58
15-48 โครงสร้างข ้อมูลและขั้นต อนว ิธี
- ท�ำค�ำส่ังในลูป while ถ้า 1 <= 10
- เปรียบเทียบค ่าส มาชิกที่ต �ำแหน่ง A[1] = 5 กับ A[10] = 53 ซ่ึงไม่เท่าก ันข ้ามเง่ือนไข if
24 - 5
- ก�ำหนดค ่า adjust = 53 - 5
= 19
48
= 0.3958
- เปรียบเทียบค่า adjust กับ 0 ซึ่งไม่น้อยก ว่า และ adjust กับ 1 ซึ่งไม่ม ากกว่า ข้ามเง่ือนไข if
- ก�ำหนดค่า mid = 1 + 0.3958 * (10-1)
≅ 5
- เปรียบเทียบเง่ือนไข x = 24 ไม่น ้อยกว่า A[mid] = A[5] = 24 ข้ามเงื่อนไข if
- เปรียบเทียบเงื่อนไข x = 24 ไม่ม ากกว่า A[mid] = A[5] = 24 ข้ามเง่ือนไข else if
- ท้ัง 2 เง่ือนไขข้างต ้นไม่เป็นจ ริงดังน้ัน x = A[5]
- ส่งค ่ากลับเป็น 5 สิ้นสุดการท�ำงาน
5 9 13 17 24 29 34 38 42 53
left = 1 mid = 5 right = 10
4. วเิ คราะห์ประสิทธิภาพของขนั้ ตอนวิธกี ารค้นหาขอ้ มลู แบบการประมาณคา่ ในชว่ ง
การว ิเคราะห์ป ระสิทธิภาพน้ันจะพ ิจารณาจ ากลักษณะการค ้นหาข ้อมูลท่ีได้ 3 แบบ ดังน้ี
4.1 กรณีด ที ีส่ ดุ
กรณีน ี้ข ้อมูลมีก ารเรียงตัวเพ่ิมข ึ้นเป็นเชิงเส้น และค ่าของข้อมูลมีก ารกร ะจ ายตัวท่ีด ี เช่น
ข้อมูลท ี่ต ้องการค ้นหา คือ 24
ข้อมูล 5 9 13 17 24 29 34 38 42 53
การค้นหาล ักษณะนี้จะมีประสิทธิภาพเชิงเวลาเท่ากับ O(log (log (n))
4.2 กรณีแ ยท่ ส่ี ดุ
กรณีน ้ีข้อมูลม ีการเรียงล �ำดับโดยค ่าที่เพิ่มข้ึนม ีการกร ะจายตัวท ี่ไม่ดี เช่น
ข้อมูลท ี่ต ้องการค ้นหา คือ 100
ข้อมูล 5 8 9 13 100 1000
ประสิทธิภาพเชิงเวลา = O( n)
4.3 กรณีทั่วไป การค้นหาข้อมูลจากข้อมูลท่ีเรียงล�ำดับแล้วด้วยวิธีการค้นหาแบบการประมาณค่าในช่วงจะ
เหมือนกับกรณีดีที่สุด คือ ข้อมูลมีการเพิ่มขึ้นแบบเชิงเส้นและค่าของข้อมูลมีการกระจายตัวที่ดี ซ่ึงประสิทธิภาพ
เชิงเวลาคือ O(log (log (n))
