Page 25 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 25
ขั้นต อนว ิธีก ารค ้นหาข้อมูล 15-15
4. วเิ คราะหป์ ระสทิ ธิภาพของขนั้ ตอนวิธกี ารคน้ หาแบบบรูทฟอร์ซ
การว ิเคราะห์ป ระสิทธิภาพนั้นจะพ ิจารณาจากลักษณะก ารค ้นหาข ้อมูลท ่ีได้ 3 แบบ ดังนี้
4.1 กรณีดที สี่ ดุ (best case)
กรณีน ี้ข้อมูลท ี่ต้องการค้นหาอ ยู่เป็นส มาชิกแ รกข องอ าร์เรย์เช่น
ข้อมูลที่ต ้องการค ้นหา คือ 9
ข้อมูล 9 1 7 5 6 3 12
การค้นหาลักษณะนี้จ ะใช้ก ารเปรียบเทียบแ ค่ครั้งเดียวเสมอ ดังนั้น ป ระสิทธิภาพเชิงเวลาเท่ากับ O(1)
4.2 กรณีแยท่ ่ีสดุ (worst case)
กรณีน ี้ข้อมูลท ี่ต้องการค ้นหาไม่มีอ ยู่ในอาร์เรย์ห รือเป็นข้อมูลตัวส ุดท้ายเช่น
ข้อมูลท ี่ต ้องการค้นหา คือ 9
ข้อมูล 1 7 5 6 3 12
การค น้ หาล กั ษณะน จี้ ะใชก้ ารเปรยี บเทยี บเทา่ กบั จ ำ� นวนข อ้ มลู ท ม่ี อี ยู่ ดงั น น้ั ป ระสทิ ธภิ าพเชงิ เวลาเทา่ กบั
O(n) 4.3 กรณีท่วั ไป (average case)
กรณีน ี้ข ้อมูลท ี่ต ้องการค้นหา อยู่ต �ำแหน่ง ใดๆ ในอ าร์เรย์เช่น
ข้อมูลท่ีต้องการค ้นหา คือ 6
ข้อมูล 1 7 5 6 3 12 n+1
2
การค้นหาลักษณะน ี้จ ะใช้ก ารเปรียบเทียบโดยเฉล่ีย ดังน ้ันประสิทธิภาพเชิงเวลาเท่ากับ O(n)
5. การนำ�ข ้นั ตอนวิธกี ารคน้ หาแบบบรทู ฟอรซ์ ไปประยุกต์ใชง้ าน
การน�ำข้ันตอนวิธีแบบบรูทฟอร์ซไปใช้งานน้ัน สามารถน�ำไปใช้ได้กับการค้นหาทุกประเภทท่ีปริมาณข้อมูล
จ�ำนวนไม่มากเน่ืองจากเป็นขั้นตอนวิธีที่ง่ายและไม่ซับซ้อน แต่ถ้าปริมาณข้อมูลมาก เวลาท่ีใช้อาจยอมรับไม่ได้
สำ� หรบั ตัวอย่างต อ่ ไปน ้ีเป็นการห าคา่ มากท ีส่ ุดและน อ้ ยท ีส่ ดุ จากข อ้ มูลท ี่ไมไ่ ด้เรยี งล �ำดบั ซึ่งว ิธกี ารหาน ั้นต้องตรวจส อบ
ทุกส มาชิกท ีละต ัว
ตวั อย่างที่ 15.4 จงแสดงวิธีการประยุกต์ใช้การค้นหาแบบบรูทฟอร์ซ ในการหาค่ามากท่ีสุดจากข้อมูลท้ังหมดที่ไม่ได้
เรียงล�ำดับ
ขั้นตอนว ิธี MaxSearch มีรายล ะเอียดดังนี้
ข้อมูลเข้าป ระกอบด้วย
อาร์เรย์ข้อมูล A
จ�ำนวนข้อมูลท ั้งหมด n
ข้อมูลท ี่ส่งก ลับ
ค่าท่ีม ากท่ีสุดจากข้อมูลท ้ังหมดในอาร์เรย์
