การค้นหาในโครงสร้างข้อมูล: อธิบายวิธีการค้นหาที่แตกต่างกัน

เครือข่ายการสื่อสารกำลังขยายตัว ดังนั้นผู้คนจึงใช้อินเทอร์เน็ต! ธุรกิจต่างๆ กำลังเข้าสู่ยุคดิจิทัลเพื่อการจัดการที่มีประสิทธิภาพ ข้อมูลที่สร้างขึ้นบนอินเทอร์เน็ตกำลังเพิ่มขึ้น ดังนั้นชุดข้อมูลจึงมีความซับซ้อน จำเป็นอย่างยิ่งที่จะต้องจัดระเบียบ จัดการ เข้าถึงและวิเคราะห์ข้อมูลอย่างรอบคอบและมีประสิทธิภาพ โครงสร้างข้อมูลเป็นเทคนิคที่มีประโยชน์ที่สุด และบทความก็เน้นที่สิ่งเดียวกัน!

โครงสร้างข้อมูล

ในวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูลเป็นพื้นฐานสำหรับชนิดข้อมูลนามธรรม (ADT) โดยที่ ADT เป็นรูปแบบตรรกะของชนิดข้อมูล เค้าโครงทางกายภาพของชนิดข้อมูลถูกนำมาใช้โดยใช้โครงสร้างข้อมูล โครงสร้างข้อมูลประเภทต่างๆ ใช้สำหรับแอปพลิเคชันประเภทต่างๆ บางคนมีความเชี่ยวชาญเฉพาะด้าน

โครงสร้างข้อมูลคือชุดของค่าข้อมูลและความสัมพันธ์ระหว่างข้อมูล การดำเนินการและฟังก์ชันที่ใช้กับข้อมูล ช่วยในการจัดระเบียบ จัดการ และจัดเก็บข้อมูลในรูปแบบเฉพาะ ผู้ใช้จึงสามารถเข้าถึงและแก้ไขข้อมูลได้อย่างมีประสิทธิภาพ

โครงสร้างข้อมูลช่วยในการจัดการข้อมูลจำนวนมาก เช่น ฐานข้อมูลขนาดใหญ่ อัลกอริทึมที่มีประสิทธิภาพสร้างขึ้นจากโครงสร้างข้อมูลที่มีประสิทธิภาพ นอกจากการจัดเก็บข้อมูลที่มีประสิทธิภาพแล้ว โครงสร้างข้อมูลยังมีหน้าที่ในการดึงข้อมูลจากหน่วยความจำที่จัดเก็บอย่างมีประสิทธิภาพอีกด้วย ประกอบด้วยอาร์เรย์ รายการที่เชื่อมโยง ตัวชี้ การค้นหา สแต็ค กราฟ คิว โครงสร้าง โปรแกรม การเรียงลำดับ และอื่นๆ

บทความนี้ครอบคลุมแนวคิดของการค้นหาในโครงสร้างข้อมูลและวิธีการ มีการอธิบายตัวอย่างอัลกอริธึมสองตัวอย่างอย่างละเอียดเพื่อให้เข้าใจแนวคิดอย่างชัดเจน เพื่อให้ได้ความรู้ ทักษะ และความเชี่ยวชาญเพิ่มเติม มีหลักสูตรออนไลน์เกี่ยวกับโครงสร้างข้อมูล ที่กล่าวถึงในตอนท้ายของบทความ

การค้นหาในโครงสร้างข้อมูลคืออะไร?

กระบวนการในการค้นหาข้อมูลที่ต้องการจากชุดของรายการที่จัดเก็บในรูปแบบขององค์ประกอบในหน่วยความจำคอมพิวเตอร์เรียกว่า 'การค้นหาในโครงสร้างข้อมูล' ชุดของรายการเหล่านี้อยู่ในรูปแบบต่างๆ เช่น อาร์เรย์ ต้นไม้ กราฟ หรือรายการที่เชื่อมโยง อีกวิธีหนึ่งในการกำหนดการค้นหาในโครงสร้างข้อมูลคือการค้นหาองค์ประกอบที่ต้องการของลักษณะเฉพาะในชุดของรายการ

วิธีค้นหา

การค้นหาในโครงสร้างข้อมูลสามารถทำได้โดยใช้อัลกอริธึมการค้นหาเพื่อตรวจสอบหรือดึงองค์ประกอบจากโครงสร้างข้อมูลที่เก็บไว้ทุกรูปแบบ อัลกอริทึมเหล่านี้จัดหมวดหมู่ตามประเภทของการดำเนินการค้นหา เช่น

• ค้นหาตามลำดับ

อาร์เรย์หรือรายการองค์ประกอบถูกสำรวจตามลำดับในขณะที่ตรวจสอบทุกองค์ประกอบของชุด

ตัวอย่างเช่น การค้นหาเชิงเส้น

• ค้นหาช่วงเวลา

อัลกอริธึมที่ออกแบบมาอย่างชัดเจนสำหรับการค้นหาในโครงสร้างข้อมูลที่เรียงลำดับจะรวมอยู่ในการค้นหาตามช่วงเวลา ประสิทธิภาพของอัลกอริธึมเหล่านี้ดีกว่าอัลกอริธึมการค้นหาเชิงเส้นมาก

ตัวอย่างเช่น การค้นหาไบนารี การค้นหาลอการิทึม

วิธีการเหล่านี้ได้รับการตรวจสอบตามเวลาที่ใช้โดยอัลกอริทึมในการค้นหาองค์ประกอบที่ตรงกับรายการค้นหาในการรวบรวมข้อมูลและกำหนดโดย

• ช่วงเวลาที่ดีที่สุด
• เวลาเฉลี่ย
• เวลาที่แย่ที่สุด

ข้อกังวลหลักเกี่ยวกับเวลาที่แย่ที่สุดที่นำไปสู่การคาดการณ์ประสิทธิภาพของอัลกอริธึมที่รับประกัน และยังคำนวณได้ง่ายเมื่อเทียบกับเวลาเฉลี่ย

เพื่อแสดงตัวอย่างและแนวคิดในบทความนี้ จะพิจารณารายการ 'n' ในการรวบรวมข้อมูลในรูปแบบข้อมูลใดๆ การดำเนินการที่โดดเด่นจะใช้เพื่อทำให้การวิเคราะห์และการเปรียบเทียบอัลกอริธึมง่ายขึ้น สำหรับการค้นหาในโครงสร้างข้อมูล การเปรียบเทียบเป็นการดำเนินการหลัก ซึ่งเขียนแทนด้วย O() และออกเสียงว่า “big-Oh” หรือ “Oh”

มีอัลกอริธึมการค้นหามากมายในโครงสร้างข้อมูล เช่น การค้นหาเชิงเส้น, การค้นหาไบนารี, การค้นหาการแก้ไข, การค้นหาข้าม, การค้นหาเลขชี้กำลัง, การค้นหา Fibonacci, การค้นหารายการย่อย, การค้นหาไบนารีที่แพร่หลาย, การค้นหาไบนารีที่ไม่มีขอบเขต, ฟังก์ชันแบบเรียกซ้ำสำหรับการค้นหาสตริงย่อย และโปรแกรมแบบเรียกซ้ำ เพื่อค้นหาองค์ประกอบเชิงเส้นในอาร์เรย์ที่กำหนด บทความนี้จำกัดเฉพาะอัลกอริธึมการค้นหาเชิงเส้นและไบนารีและหลักการทำงาน

มาดูข้อมูลเชิงลึกโดยละเอียดเกี่ยวกับการค้นหาเชิงเส้นและการค้นหาแบบไบนารีในโครงสร้างข้อมูล

ค้นหาเชิงเส้น

อัลกอริธึมการค้นหาเชิงเส้นจะค้นหาองค์ประกอบทั้งหมดในอาร์เรย์ตามลำดับ เวลาดำเนินการที่ดีที่สุดคือครั้งเดียว ในขณะที่เวลาดำเนินการที่แย่ที่สุดคือ n โดยที่ n คือจำนวนรายการทั้งหมดในอาร์เรย์การค้นหา

เป็นอัลกอริธึมการค้นหาที่ง่ายที่สุดในโครงสร้างข้อมูลและตรวจสอบแต่ละรายการในชุดขององค์ประกอบจนกว่าจะตรงกับองค์ประกอบการค้นหาจนกว่าจะสิ้นสุดการรวบรวมข้อมูล เมื่อไม่มีการจัดเรียงข้อมูล ควรใช้อัลกอริธึมการค้นหาเชิงเส้น

การค้นหาเชิงเส้นมีความซับซ้อนดังนี้:

• ความซับซ้อนของอวกาศ

ความซับซ้อนของพื้นที่สำหรับการค้นหาเชิงเส้นคือ O(n) เนื่องจากไม่ได้ใช้ช่องว่างเพิ่มเติมโดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์

• ความซับซ้อนของเวลา

*ความซับซ้อนของกรณีที่ดีที่สุด = O(1) เกิดขึ้นเมื่อองค์ประกอบการค้นหาอยู่ที่องค์ประกอบแรกในอาร์เรย์การค้นหา

*Worst- case complexity = O(n) เกิดขึ้นเมื่อองค์ประกอบการค้นหาไม่มีอยู่ในชุดขององค์ประกอบหรืออาร์เรย์

*ความซับซ้อนเฉลี่ย = O(n) ถูกอ้างถึงเมื่อองค์ประกอบนั้นอยู่ที่ใดที่หนึ่งในอาร์เรย์การค้นหา

ตัวอย่าง,

ลองใช้อาร์เรย์ขององค์ประกอบตามที่ระบุด้านล่าง:

45, 78, 12, 67, 08, 51, 39, 26

ในการค้นหา '51' ในอาร์เรย์ของ 8 องค์ประกอบที่ระบุข้างต้น อัลกอริธึมการค้นหาเชิงเส้นจะตรวจสอบแต่ละองค์ประกอบตามลำดับจนกระทั่งตัวชี้ชี้ไปที่ 51 ในพื้นที่หน่วยความจำ ต้องใช้เวลา O(6) ในการค้นหา 51 ในอาร์เรย์ ในการค้นหา 12 ในอาร์เรย์ด้านบน จะใช้เวลา O(3) ในขณะที่ 26 จะใช้เวลา O(8)

ค้นหาไบนารี

อัลกอริทึมนี้ค้นหารายการเฉพาะโดยการเปรียบเทียบรายการที่อยู่ตรงกลางสุดในการรวบรวมข้อมูล เมื่อการจับคู่เกิดขึ้น จะส่งกลับดัชนีของรายการ เมื่อรายการกลางมีค่ามากกว่ารายการ รายการกลางจะค้นหารายการกลางของอาร์เรย์ย่อยด้านซ้าย ในทางตรงกันข้าม หากรายการกลางมีขนาดเล็กกว่ารายการค้นหา รายการนั้นจะสำรวจตรงกลางของรายการในอาร์เรย์ย่อยด้านขวา ยังคงค้นหารายการต่อไปจนกว่าจะพบหรือจนกว่าขนาดอาร์เรย์ย่อยจะกลายเป็นศูนย์

การค้นหาแบบไบนารีต้องการการเรียงลำดับของรายการ เร็วกว่าอัลกอริธึมการค้นหาเชิงเส้น มันทำงานบนหลักการแบ่งแยกและพิชิต

ความซับซ้อนรันไทม์ = O(log n)

อัลกอริทึมการค้นหาแบบไบนารีมีความซับซ้อนดังนี้:

• ความซับซ้อนของกรณีที่เลวร้ายที่สุด = O (n บันทึก n)
• ความซับซ้อนเฉลี่ย = O (n บันทึก n)
• ความซับซ้อนของกรณีที่ดีที่สุด = O (1)

ตัวอย่าง,

ลองใช้อัลกอริทึมการเรียงลำดับของ 08 องค์ประกอบ:

08, 12, 26, 39, 45, 51, 67, 78

ในการค้นหา 51 ในอาร์เรย์ขององค์ประกอบข้างต้น

อัลกอริธึมจะแบ่งอาร์เรย์ออกเป็นสองอาร์เรย์ 08, 12, 26, 39 และ 45, 51, 67, 78

เนื่องจาก 51 มากกว่า 39 ระบบจะเริ่มค้นหาองค์ประกอบทางด้านขวาของอาร์เรย์

มันจะแบ่งออกเป็นสองเพิ่มเติมเช่น 45, 51 และ 67, 78

เนื่องจาก 51 มีขนาดเล็กกว่า 67 มันจะเริ่มค้นหาทางด้านซ้ายของอาร์เรย์ย่อยนั้น

subarray นั้นถูกแบ่งออกเป็นสองอีกครั้งเป็น 45 และ 51

เนื่องจาก 51 เป็นตัวเลขที่ตรงกับองค์ประกอบการค้นหา ระบบจะส่งคืนหมายเลขดัชนีขององค์ประกอบนั้นในอาร์เรย์

จะสรุปได้ว่าองค์ประกอบการค้นหา 51 อยู่ที่ตำแหน่งที่ 6 ในอาร์เรย์

การค้นหาแบบไบนารีช่วยลดเวลาลงเหลือครึ่งหนึ่งเนื่องจากจำนวนการเปรียบเทียบลดลงอย่างมากเมื่อเทียบกับอัลกอริธึมการค้นหาเชิงเส้น

อ่าน: ประเภทของโครงสร้างข้อมูลใน Python

ค้นหาการแก้ไข

เป็นตัวแปรที่ได้รับการปรับปรุงของอัลกอริธึมการค้นหาแบบไบนารีและทำงานในตำแหน่งการตรวจสอบขององค์ประกอบการค้นหา คล้ายกับอัลกอริธึมการค้นหาแบบไบนารี มันทำงานอย่างมีประสิทธิภาพในการรวบรวมข้อมูลที่เรียงลำดับเท่านั้น

เวลาดำเนินการที่แย่ที่สุด = O(n)

เมื่อทราบตำแหน่งขององค์ประกอบเป้าหมายในการรวบรวมข้อมูล การค้นหาการแก้ไขจะถูกใช้ หากต้องการค้นหาหมายเลขในสมุดโทรศัพท์ หากต้องการค้นหาหมายเลขโทรศัพท์ของ Monica แทนที่จะใช้การค้นหาแบบเชิงเส้นหรือแบบไบนารี ผู้ใช้สามารถตรวจสอบพื้นที่เก็บข้อมูลหน่วยความจำโดยตรงโดยที่ชื่อขึ้นต้นด้วย 'M'

บทสรุป

การค้นหาในโครงสร้างข้อมูลหมายถึงการค้นหาองค์ประกอบที่กำหนดในอาร์เรย์ขององค์ประกอบ 'n' มีสองประเภท ได้แก่ การค้นหาตามลำดับและการค้นหาตามช่วงเวลาในการค้นหา อัลกอริธึมการค้นหาเกือบทั้งหมดขึ้นอยู่กับหนึ่งในสองหมวดหมู่นี้ การค้นหาเชิงเส้นและไบนารีเป็นอัลกอริธึมที่ใช้งานง่ายสองอัลกอริธึมซึ่งไบนารีทำงานได้เร็วกว่าอัลกอริธึมเชิงเส้น

แม้ว่าการค้นหาเชิงเส้นจะตรงไปตรงมาที่สุด แต่จะตรวจสอบแต่ละองค์ประกอบจนกว่าจะพบรายการที่ตรงกับองค์ประกอบการค้นหา ซึ่งจะมีประสิทธิภาพเมื่อการรวบรวมข้อมูลไม่ได้จัดเรียงอย่างถูกต้อง แต่ถ้าการรวบรวมข้อมูลถูกจัดเรียงและความยาวของอาร์เรย์มีมาก การค้นหาแบบไบนารีก็จะเร็วขึ้น

โครงสร้างข้อมูลเป็นส่วนสำคัญของการเขียนโปรแกรมคอมพิวเตอร์ในขณะที่จัดการกับชุดข้อมูล โปรแกรมเมอร์และนักพัฒนาจำเป็นต้องอัปเดตและเพิ่มทักษะด้วยตนเองด้วยพื้นฐานและการอัปเดตในเทคนิคการเขียนโปรแกรมคอมพิวเตอร์ โปรแกรมเมอร์ที่เกี่ยวข้องกับโครงสร้างข้อมูลควรเลือกเรียนหลักสูตรบ่อยๆ

หากคุณอยากทราบข้อมูลเพิ่มเติมเกี่ยวกับวิทยาศาสตร์ข้อมูล โปรดดูที่ IIIT-B & upGrad's Executive PG Program in Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพด้านการทำงานและเสนอกรณีศึกษาและโครงการมากกว่า 10 รายการ การประชุมเชิงปฏิบัติการเชิงปฏิบัติ การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม ตัวต่อตัวกับที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ

เตรียมความพร้อมสู่อาชีพแห่งอนาคต

หลักสูตรประกาศนียบัตรขั้นสูงด้านวิทยาศาสตร์ข้อมูล