Algorithms

วัตถุประสงค์

• เรียนรู้หลักการของการค้นหาข้อมูลแบบต่างๆ
• เรียนรู้การวิเคราะห์อัลกอริทึมจากการค้นหาข้อมูลแบบต่างๆ
• ทดลองและวิเคราะห์การใช้งานอัลกอริทึมในการค้นหาข้อมูลแบบต่างๆ

การค้นหาแบบลำดับ Linear Search

1.อ่านอาร์เรย์ทีละตัว A แล้วเปรียบเทียบกับคีย์ X ที่ต้องการค้นหา
2. ถ้า A เท่ากับ X เจอข้อมูลที่ค้นหา ส่งค่าตำแหน่งที่เจอข้อมูลกลับคืน
3. ถ้าอ่านจนหมดแล้ว แสดงว่าหาไม่เจอ ส่งค่า -1 กลับคืน

ฟังก์ชัน Linear Search -->> Top

ตัวอย่างโปรแกรม Linear Search

การวิเคราะห์ค่า Big O ของ Linear Search

Linear Search ค้นหาที่ละตัว ใช้เวลาเท่ากับจำนวนข้อมูลที่มีอยู่ หรือ O (N)

การค้นหาข้อมูลที่มีค่าสูงสุด (Find Maximum)
1. กำหนดข้อมูลตัวแรกให้มีค่าสูงสุด max = first_item;
2. เปรียบเทียบข้อมูลทั้งหมดทีละตัวกับค่าสูงสุด ถ้าข้อมูลตัวปัจจุบันมีค่ามากกว่าค่าสูงสุด ให้กำหนดข้อมูลนั้นเป็นค่าสูงสุด If (current_item > max) max = current_item;
3. เปรียบเทียบข้อมูลตัวถัดไปเรื่อยๆ จนหมดข้อมูล current_item = next_item;
4. ส่งคืนค่าสูงสุด return max;

ฟังก์ชัน FindMax -->> Top

ตัวอย่างโปรแกรม FindMin FindMax

รูปที่ 1.1: Factorial Function Recursion

การวิเคราะห์ค่า Big O ของ FindMax

การค้นหาค่าสูงสุด มีการเปรียบข้อมูลทุกตัว (N) ดังนั้นค่า Big O คือ O(N)

การค้นหาข้อมูลแบบแบ่งครึ่ง Binary Search -->> Top

การค้นหาแบบนี้ใช้หลักการชองแบ่งแยกแล้วรวม (divide and conquer) สามารถใช้ได้กับข้อมูลที่มีการเรียงลำดับแล้วเท่านั้น ซึ่งจะต้องใช้เวลาในการเรียงข้อมูลทั้งหมดก่อนที่จะทำการค้นหาข้อมูลแบบไบนารีได้ แต่อย่างไรก็ตามเราใช้เวลาในการเรียงข้อมูลเพียงครั้ง เดียวเท่านั้น หลังจากนั้นสามารถทำการค้นหาข้อมูลได้ตลอด ซึ่งถ้าเทียบกับการค้นหาแบบลำดับแล้ว การค้นหาแบบไบนารี มีประสิทธิภาพดีกว่าแบบลำดับ

Binary Search Algorithm

1. ค้นหาข้อมูลกึ่งกลาง m ของข้อมูลทั้งหมดซึ่งแบ่งข้อมูลเป็นสองส่วน แล้วทำการปรียบเทียบข้อมูลกึ่งกลาง m กับค่า key ที่ต้องการค้นหา
2. ถ้า key น้อยกว่า m ให้ค้นหาในรอบต่อไปจากข้อมูลทั้งหมดทางด้านซ้ายของ m โดยทำซ้ำข้อ 1
3. ถ้า key มากกว่า m ให้ค้นหาในรอบต่อไปจากข้อมูลทั้งหมดทางด้านขวาของ m โดยทำซ้ำข้อ 1
4. ถ้า key เท่ากับ m เราเจอข้อมูลที่ต้องการ ส่งค่าตำแหน่งที่เจอกลับไป
5. ถ้าแบ่งจนหมดแล้วยังไม่เจอ ส่งค่า -1 กลับคืน

ฟังก์ชัน Binary Search -->> Top

ตัวอย่างการค้นหาแบบไบนารี

1. ค้นหา 17 จากอาร์เรย์ต่อไปนี้: 1, 3, 4, 5, 17, 18, 31,33

2. ค้นหา 2 จากอาร์เรย์ต่อไปนี้: 1, 3, 4, 5, 17, 18, 31,33

ตัวอย่างโปรแกรม Binary Search

การวิเคราะห์ค่า Big O ของ Binary Search

การค้นหาแบบไบนารีมีการแบ่งครึ่งแล้วค้นหามีการเปรียบข้อมูลทุกตัว (log N) ดังนั้นค่า Big O คือ O( log N)

สรุป -->> Top