วิทยาการคำนวณ 1 เรื่อง 1.8 การค้นหาข้อมูล

กิจกรรมที่ 8 การค้นหาข้อมูล
ตัวชี้วัด ประยุกต์ใช้แนวคิดเชิงคำนวณในการพัฒนาโครงงานที่มีการบูรณาการกับวิชาอื่นอย่างสร้างสรรค์และเชื่อมโยงกับชีวิตจริง
สาระการเรียนรู้ ขั้นตอนในการค้นหาข้อมูล เช่น การค้นหาแบบลำดับและการค้นหาแบบทวิภาค
การค้นหาข้อมูล
    การค้นหาข้อมูลที่มีประสิทธิภาพนั้น ขึ้นอยู่กับหลักการค้นหา รวมถึงขั้นตอนของการค้นหานั้น การค้นหาข้อมูลพื้นฐานมีหลากหลายวิธี เช่น การค้นหาข้อมูลแบบลำดับ การค้นหาข้อมูลแบบทวิภาค และการค้นหาข้อมูลแบบแฮชชิง
    การใช้เทคนิคการค้นหาข้อมูลแบบใดต้องดูลักษณะของงาน ซึ่งจะช่วยให้เราสามารถตัดสินใจเลือกเทคนิคการค้นหาข้อมูลที่เหมาะสมได้                    
การค้นหาข้อมูลแบบลำดับ(Sequential Search)
    การค้นหาข้อมูลแบบลำดับ(Sequential Search) การหาข้อมูลแบบเป็นลำดับขั้นตอน โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ หรือเปรียบเทียบไปจนถึงตัวสุดท้าย การค้นหาวิธีนี้เป็นวิธีที่ง่ายที่สุด  อัลกอริทึ่มในการค้นหาไม่ซับซ้อนสามารถใช้กับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่ยังไม่ได้เรียงลำดับก็ได้ โดยผลลัพธ์จากการค้นหาข้อมูลจะมีความเป็นไปได้อยู่ 2 แบบ คือ
     1.พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์(Successful Search)
    2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)


การค้นหาข้อมูลแบบทวิภาค (Binary Serach) 
    การค้นหาข้อมูลแบบทวิภาค เหมาะสำหรับค้นหาข้อมูลที่มีการเรียงลำดับอยู่แล้ว โดยการค้นหาแต่ละรอบจะลดขอบเขตการค้นหาลงทีละครึ่ง
    การค้นหาข้อมูลแบบทวิภาคมีประสิทธิภาพดีมากและเป็นแนวคิด หลักในการพัฒนาระบบฐานข้อมูล  หลังพิจารณาข้อมูลแต่ละครั้ง ขอบเขตของดัชนีที่เป็นไปได้จะลดลงประมาณครึ่งหนึ่ง ถ้าข้อมูลในรายการมีจำนวน n ตัว จำนวนรอบที่ต้องทํางานจะเท่ากับจําานวนครั้งในการลดค่าขอบเขตที่เป็นไปได้จาก n ทีละครึ่งจนเหลือค่าเท่ากับ 1 ซึ่งค่าดังกล่าวสอดคล้อง กับฟังก์ชันลอการิทึม (logarithm) ฐาน 2 ของ n ดังนั้นความซับซ้อนของ ขั้นตอนวิธีการค้นหาแบบทวิภาคจะแปรผันตรงกับ log2 n นั่นคือเรา สามารถเขียนว่าการค้นหาแบบทวิภาคมีความซับซ้อนเป็น O(log2 n)
เทคนิคการค้นหาข้อมูลด้วยวิธีนี้
    1. กำหนดข้อมูลที่ต้องการค้นหาและทำการเรียงข้อมูลตามความต้องการ เรียงจากมากไปน้อย หรือจากน้อยไปมากก็ได้
    2. ทำการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วทำการหาค่ากลาง
    3. เมื่อทราบแล้วว่าค่าของคีย์ฟิลด์อยู่ครึ่งแรกหรือครึ่งหลังแล้ว ก็จะนำข้อมูลในครึ่งดังกล่าวทำการหาค่ากลางอีก ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งได้ข้อมูลที่ต้องการ หรือจนกระทั่งไม่สามารถแบ่งข้อมูลได้อีก
     ตัวอย่างการค้นหา
เปรียบเทียบระหว่าง Sequential Search และ Binary Search
        การเปรียบเทียบครั้งนี้ จะใช้ Binary Search เป็นตัวอ้างอิง ซึ่งเราจะแบ่งออกเป็น  2   ประเภท คือ 
         1. Best Case Binary Search
       2.Worst Case Binary Search
    จะเห็นได้ว่า Binary Search สามารถหาข้อมูลที่ต้องการได้เร็วกว่า Sequential Search เมื่อมีจำนวนข้อมูลจำนวนมาก แต่ถ้าหากมีข้อมูลน้อยๆ และสิ่งที่ต้องการหานั้นอยู่เป็นต้นๆก็จำทำให้การหาแบบ Sequential Search เร็วกว่า ดังกราฟ
โดยที่ n = Sequential Search
log(n) = Binary Search

ที่มา : http://cs60052016.blogspot.com/2016/10/sequential-search-vs-binary-search.html
Comments