Page 31 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 31
ขั้นตอนวิธีก ารค ้นหาข้อมูล 15-21
รอบท่ี 2
5 24 33 43 68 73 90 91
i = 2, A[2] = 24
X = 34
- เปรียบเทียบค่าสมาชิกตัวแรกโดยม ีค ่าด ัชนี i = 2, A[2] = 24 กับ 34 ซึ่งไม่เท่ากัน
- เปรียบเทียบค่า x = 34 กับค่า 24 ซึ่งค ่า x มากกว่า ให้เปรียบเทียบค ่าถัดไป
รอบท่ี 3
5 24 33 43 68 73 90 91
i = 3, A[3] = 33
X = 34
- เปรียบเทียบค ่าส มาชิกตัวแ รก โดยมีค่าดัชนี i = 3, A[3] = 33 กับ 34 ซ่ึงไม่เท่ากัน
- เปรียบเทียบค ่า x = 34 กับค่า 33 ซึ่งค่า x มากกว่า ให้เปรียบเทียบค ่าถ ัดไป
รอบที่ 4 – รอบส ุดท้าย
5 24 33 43 68 73 90 91
i = 4, A[4] = 43
X = 34
- เปรียบเทียบค ่าสมาชิกตัวท่ีส ี่โดยม ีค ่าด ัชนี i = 4, A[4] = 43 กับ 34 ซ่ึงไม่เท่าก ัน
- เปรยี บเทยี บคา่ x = 34 กบั ค า่ 43 ซง่ึ คา่ x นอ้ ยก วา่ โปรแกรมห ยดุ ทำ� งานแ ละใหค้ า่ ก ลบั เปน็ ไมพ่ บ นน่ั คอื -1
4. วิเคราะห์ประสทิ ธภิ าพของการคน้ หาขอ้ มูลแบบเรยี งล�ำ ดับ
การว ิเคราะห์ประสิทธิภาพน ้ันจะพ ิจารณาจ ากล ักษณะก ารค ้นหาข ้อมูลท ่ีได้ 3 แบบ ดังนี้
4.1 กรณีดที ่สี ุด
กรณีน ี้ข้อมูลท่ีต ้องการค้นหาอ ยู่เป็นสมาชิกแรกของอาร์เรย์เช่น
ข้อมูลที่ต้องการค้นหา คือ 1
ข้อมูล 1 7 15 16 23 32
การค้นหาลักษณะนี้จ ะใช้ก ารเปรียบเทียบแ ค่ค รั้งเดียวเสมอดังน้ันประสิทธิภาพเชิงเวลาเท่ากับ O(1)
4.2 กรณแี ย่ที่สุด
กรณีน ้ีข ้อมูลท ี่ต ้องการค้นหามีค่าม ากกว่าค ่าตัวส ุดท้ายห รือเป็นข ้อมูลตัวสุดท้ายข องอ าร์เรย์เช่น
ข้อมูลท ี่ต ้องการค้นหา คือ 33
ข้อมูล 1 7 15 16 23 32
การค้นหาลักษณะน้ีจะใช้การเปรียบเทียบเทา่ กับจำ� นวนข้อมูลท่ีอยู่ ดังนนั้ ประสทิ ธิภาพเชิงเวลาเท่ากบั
O(n)
