โครงสร้างข้อมูล/บทนำ

เรื่องสามเรื่องที่ไม่เกี่ยวกัน

เรื่องที่หนึ่ง

คุณคิดว่าซอฟต์แวร์ที่คุณใช้เกิดจากโปรแกรมกี่บรรทัด? (ยกตัวอย่างเช่น ระบบปฏิบัติการ Linux หรือคอมไพเลอร์ภาษาซีของ gnu) บางโปรแกรมนั้นยาวมากถึงระดับเป็นล้านบรรทัด! คุณคิดว่าโปรแกรมเมอร์ทราบได้อย่างไรว่าโปรแกรมนั้นทำงานได้ถูกต้อง? คุณคิดว่าทุกคนในทีมพัฒนาโปรแกรมได้อ่านซอร์สโค้ตทุกบรรทัดหรือ?

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

เรื่องที่สอง

ทำไมเราถึงมีรถยนต์ใช้? คำตอบง่ายๆ ก็คือเพราะว่าเรารู้จักการใช้ล้อ เรารู้จักการสร้างเครื่องยนต์ การหล่อโลหะ ฯลฯ.

โลกของการคิดค้นเปลี่ยนหน้าตาไป เมื่อมนุษย์รู้จักการสร้างล้อที่หมุนได้ และรู้จักที่จะเปิดเผยให้ผู้อื่นมองเห็นว่าล้อมีลักษณะเช่นใด. การค้นพบที่ ``ง่าย และมีประโยชน์อย่างใหญ่หลวงได้มีคนทำไปหมดแล้ว: ล้อ ไฟ ลูกตุ้มนาฬิกา เข็มทิศ ระบบการพิมพ์ หลอดไฟ สารกึ่งตัวนำ ทรานซิสเตอร์ คอมพิวเตอร์ เม้าส์ ระบบหน้าต่าง Linux ฯลฯ. (คำว่า ``ง่าย ที่ใช้ในที่นี้ไม่ได้ใช้เพื่อบอกว่าความพยายามที่ต้องใช้ก่อนที่จะค้นพบสิ่งเหล่านี้ไม่ได้มีอย่างมหาศาล. คำว่าง่าย ใช้ในความหมายเดียวกับคำว่า ``simple ที่ตรงกันข้ามกับคำว่าซับซ้อน.) แต่การที่ทุกคนไม่จำเป็นที่จะต้องเป็นนักคิดผู้ยิ่งใหญ่เพียงเพื่อจะได้มีแสงสว่างใช้ในเวลากลางคืนนั้น เป็นการประหยัดเวลาและทรัพยากรของคนเราอย่างยิ่งยวด.

เรื่องที่สาม

ทำไมตอนนี้เราจึงมีข้าวกินโดยไม่ต้องทำนา? ทำไมเราถึงสามารถเดินทางไปไหนมาไหนได้โดยไม่จำเป็นต้องขับรถยนต์เป็น? ทำไมเรามีเพลงฟังได้โดยไม่จำเป็นต้องเล่นดนตรีเป็น?

เมื่อสังคมได้พัฒนาผ่านสังคมยุคการเกษตรที่ทุกคนมีความสามารถจะกระทำกิจกรรมต่างๆ ที่จำเป็นในการดำรงชีพได้ด้วยตนเอง ไปสู่สังคมที่ซับซ้อนขึ้น สิ่งทีเกิดขึ้นก็คือความยุ่งยากในการจัดการกิจกรรมแต่ละส่วนของสังคม. เราจัดการกับปัญหานี้โดยการกำหนดให้บุคคลบางคน หรือบางกลุ่มไปมีหน้าที่ต้องเรียนรู้ และจัดการกับงานในส่วนนั้นๆ ของสังคมโดยเฉพาะ. ด้วยเหตุนี้ผู้เชี่ยวชาญเฉพาะด้านก็เกิดขึ้น. ผู้ยังไม่เชี่ยวชาญอย่างเราถึงได้มีสังคมที่ทำงานไปได้อาศัยอยู่ (โดยไม่รู้เลยว่าในแต่ละส่วนนั้นมันสามารถดำเนินไปได้อย่างไร).

แนวคิดหลักทั้งสาม: การมองปัญหาแบบภาพรวม (abstraction) การใช้สิ่งที่คิดค้นมาแล้ว (reuse) และการแบ่งงาน (division of labors) เป็นฐานของการพัฒนาของอารยธรรมมนุษย์. เป้าหมายของมันก็คือ การจัดการกับความซับซ้อน!!!

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

ตัวอย่าง

เราจะเริ่มจากตัวอย่างสองตัวอย่าง.

เกมสามมิติ

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

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

เพื่อความง่ายในการทำความเข้าใจ เราจะมองปัญหาในสองมิติ. เรามีรูปเหลี่ยมมากมาย แต่ในขณะหนึ่งเรามีมุมมองที่จำกัดอยู่ขอบเขตสี่เหลี่ยมอันหนึ่งเท่านั้น. เราต้องการจะหาวัตถุทั้งหมดที่ปรากฏอยู่ในขอบเขตนั้น. สมมติว่าเรามีวัตถุในฉากทั้งหมด $n$ ชิ้น. ถ้าเราต้องใช้เวลาในการตรวจสอบวัตถุทุกชิ้น เวลาที่เราจะต้องใช้ อย่างน้อยก็จะต้องแปรผันตรงกับจำนวนของวัตถุทั้งหมด. เราจะมีวิธีใดๆ หรือไม่ ที่จะทำให้เราไม่ต้องไปพิจารณาวัตถุทั้งหมดโดยไม่จำเป็น?

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

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

โครงสร้างข้อมูลที่เราจะใช้เรียกว่า quad tree. เนื่องจากมันมีลักษณะเป็นต้นไม้ที่เกิดจากการแบ่งพื้นที่ออกเป็นสี่ส่วน. เริ่มต้นที่รูปดังกล่าว เราจะแบ่งพื้นที่ออกเป็นสี่ส่วนโดยใช้เส้นแบ่งสองอัน (ดูรูปถัดไป). เราจะพบว่าถ้ามุมมองของเราอยู่แค่ในส่วนหนึ่งส่วนใดของพื้นที่ทั้งสี่นี้แล้ว (เช่นอยู่ในมุมบนขวา) ในการพิจารณาวัตถุต่างๆ เราไม่จำเป็นที่จะต้องไปคำนึงถึงวัตถุที่ในมุมล่างซ้าย เป็นต้น. เราอาจจะมีปัญหาอยู่บ้างสำหรับวัตถุที่อยู่ระหว่างเส้นแบ่ง ซึ่งเราไม่สามารถจะจัดให้มันอยู่ในกลุ่มไหนได้ เราจึงต้องแยกวัตถุกลุ่มนี้เอาไว้ และไม่ว่ามุมมองของเราจะอยู่ที่จุดไหน เราก็จะต้องตรวจสอบวัตถุในกลุ่มนี้เสมอ.

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

สังเกตว่าการแบ่งของเรามีลักษณะเป็นลำดับชั้น โดยที่การแบ่งพื้นที่ครั้งแรกจะเป็นการแบ่งชั้นบนสุด. จากนั้นก็จะเป็นการแบ่งที่ลำดับชั้นเล็กๆ ลงไป. เมื่อเราได้การแบ่งทุกลำดับชั้นแล้ว เราสามารถจะสร้าง quad tree สำหรับการค้นหาวัตถุที่อยู่ในมุมมองได้ดังรูปถัดไป. (การแบ่งที่อยู่ในชั้นเล็กกว่าลำดับที่สามได้ถูกละเอาไว้.)

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

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

สมุดโทรศัพท์

เราสามารถมองสมุดโทรศัพท์เป็นโครงสร้างข้อมูลแบบหนึ่ง. สิ่งที่สำคัญอย่างแรกที่เราต้องพิจารณาก็คือส่วนติดต่อ (interface) ของโครงสร้างข้อมูล. สำหรับสมุดโทรศัพท์ สิ่งที่เรามีก็คือ กระดาษเป็นหน้าๆ เราสามารถเปิดไปที่หน้าใดก็ได้ (โดยไม่จำเป็นต้องเปิดไปทีละหน้า) ในแต่ละหน้า เราก็จะมีีรายชื่อของผู้ใช้โทรศัพท์ พร้อมกับเบอร์โทรศัพท์. ที่ด้านหน้าเราจะมีสารบัญ (หรือดัชนี) ที่ชี้เลขหน้าเริ่มต้นของรายชื่อที่ขึ้นต้นด้วยตัวอักษรต่างๆ. ที่สำคัญที่สุดก็คือเราทราบว่า รายชื่อในสมุดโทรศัพท์เรียงตามลำดับตัวอักษร. ในส่วนนี้เราจะยกตัวอย่างวิธีการค้นเบอร์โทรศัพท์หลายๆ แบบ และลองคิดคำนวนคร่าวๆ ว่าเวลาที่ใช้ในการค้นหาเป็นเท่าใด. เราสมมติว่าเรามีรายชื่อในสมุดโทรศัพท์ทั้งสิ้น $n$ รายชื่อ และ (เพื่อความง่ายในการวิเคราะห์) ในแต่ละหน้า เราสมมติว่าสามารถเก็บรายชื่อได้คนเดียว.

การค้นหาแบบตามลำดับ

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

ถ้าชื่อของคนที่เราต้องการค้นหานั้นอยู่ในหน้าแรก เวลาที่เราใช้ในการค้นหาก็จะมีค่าคงที่เสมอ ไม่ว่าสมุดโทรศัพท์นั้นจะหนาเท่าใดก็ตาม. ในทางกลับกันถ้าชื่อนั้นเป็นชื่อสุดท้าย การค้นหาก็จะใช้เวลาเท่ากับเวลาที่ใช้ในการเปิดหน้ากระดาษ $n$ ครั้ง. เนื่องจากคนที่เปิดสมุดโทรศัพท์มีความเร็วในการเปิดในแต่ละหน้าไม่เท่ากัน การที่เราจะกล่าวว่าเวลาที่ใช้คือ $n$ วินาที ก็คงจะไม่ถูกต้องนัก. แต่ถ้าเราลองพิจารณาว่า เราวิเคราะห์เวลาการทำงานไปทำไม เราจะพบว่าเราวิเคราะห์ไปเพื่อความสะดวกในการเปรียบเทียบเวลาการทำงานของวิธีการหลายๆ อัน และโดยปกติแล้ว เราต้องการทราบเวลาการทำงานคร่าวๆ เมื่อข้อมูลมีเป็นจำนวนมาก. ในที่นี้เราจะเขียนว่าวิธีการค้นหาแบบตามลำดับนั้น ใช้เวลา $O(n)$ ในการค้นหา. สัญลักษณ์ $O(\cdot )$ (อ่านว่า Big-O) นี้เป็นสัญลักษณ์ที่ใช้ระบุว่าฟังก์ชั่นที่เราพิจารณาอยู่นั้นมีพฤติกรรมเป็นเช่นใดเมื่อขนาดของ $n$ มีค่ามากขึ้น. เราจะศึกษาเรื่องของโดยละเอียดต่อไปอีกครั้งหนึ่ง. ในที่นี้ขอให้ผู้อ่านเข้าใจไปคร่าวๆ ก่อนว่ามันคือวิธีการพิจารณาฟังก์ชั่นที่ไม่สนใจค่าคงที่ และค่าที่มีความสำคัญน้อยต่อการ "โต" ของฟังก์ชั่น. สำหรับการค้นหาแบบนี้ ถ้าเป็นกรณีที่ดีที่สุดแล้ว เราจะใช้เวลา $O(1)$ นั่นคือ ใช้เวลาเป็นค่าคงที่. โดยทั่วไป เราจะให้ความสำคัญมากกว่ากับเวลาที่ใช้ในกรณีที่แย่ที่สุด.

การค้นหาโดยใช้สารบัญและตามด้วยการหาแบบตามลำดับ

เมื่อเราพิจารณาข้อมูลต่างๆ ที่สมุดโทรศัพท์มีเพื่อช่วยเราในการค้นหาแล้ว เราจะพบว่า เราสามารถใช้สารบัญเพื่อหาชื่อที่ต้องการได้ง่ายขึ้น. แต่ถ้าเรามองกรณีที่แย่ที่สุด เราอาจจะพบว่ามันเป็นไปได้ที่ชื่อทุกชื่อจะมีตัวอักษรเริ่มต้นเหมือนกันหมด ดังนั้น สารบัญที่เขียนขึ้นโดยใช้ตัวอักษรต้นเท่านั้น ก็มิได้ช่วยให้เราค้นหาชื่อได้เร็วขึ้น นั่นคือเราก็ยังใช้เวลา $O(n)$ เท่าเดิม. สิ่งที่เราต้องการจากสารบัญก็คือการแบ่งข้อมูลออกเป็นกลุ่มย่อยๆ เพื่อลดเวลาในการค้นหาที่ไม่จำเป็นลง. ในที่นี้ ถ้าการสร้างสารบัญทำได้อย่างมีประสิทธิภาพ เราหวังว่า ถ้าเราใช้สารบัญที่มีขนาด $r$ เราจะใช้เวลาในการค้นชื่อ $O(n/r)$. แต่การปรับปรุงนี้ก็ไม่ได้มาฟรีๆ เราต้องใช้เวลา $O(r)$ ในการค้นที่สารบัญอีก. ดังนั้นเวลาที่ใช้ทั้งหมดก็คือ $O(r+n/r)$. เราสามารถกำหนดให้ $r={\sqrt {n}}$ เพื่อทำให้เวลาที่ใช้ทั้งเป็น $O({\sqrt {n}}+n/{\sqrt {n}})=O({\sqrt {n}})$ ซึ่งเร็วขึ้นกว่า $O(n)$ ที่เป็นเวลาที่ใช้ถ้าเราไม่ใช้สารบัญ (หรือใช้สารบัญที่ออกแบบไม่ดีพอ).

การค้นหาแบบทวิภาค

คุณสมบัติอีกอันหนึ่งของสมุดโทรศัพท์ที่เรายังไม่ได้นำมาใช้ ก็คือการที่รายชื่อทั้งหมดถูกเรียงกันตามลำดับ. ดังนั้น ถ้าเราเปิดดูรายชื่ออยู่ที่หน้าใดหน้าหนึ่ง เราสามารถบอกได้ทันทีว่า ชื่อที่เราต้องการหานั้น อยู่ที่หน้าที่อยู่ก่อนหน้า หรืออยู่หลังหน้าที่เรากำลังพิจารณาอยู่ โดยใช่้การเปรียบเทียบ. ดังนั้น สิ่งที่เราทำได้ก็คือ เมื่อเริ่มต้น เราเปิดไปที่หน้ากลาง จากนั้นพิจารณาว่ารายชื่อที่เราต้องการค้นหานั้น อยู่ที่ส่วนต้น หรือส่วนปลายของสมุดโทรศัพท์. ในการเปรียบเทียบแต่ละครั้ง เราลดขนาดของสมุดโทรศัพท์ลงครึ่งหนึ่ง. เราจะได้ว่า ถ้าเราลดขนาดของสมุดโทรศัพท์ลงจนทำให้เราเหลือหน้ากระดาษแค่หนึ่งหน้า เราก็จะได้คำตอบ. ถ้าเริ่มต้น เรามีสมุดโทรศัพท์จำนวน $n$ หน้า เราจะต้องเปรียบเทียบทั้งสิ้น $O(\log _{2}n)$ ครั้ง. (โดยทั่วไปแล้ว เราสามารถละฐานของลอกการิทึม ได้ เนื่องจากเมื่อเราใช้เครื่องหมาย $O$ แล้ว $O(\log _{10}n)=O(\log _{2}n)=O(\log _{c}n)$ สำหรับค่าคงที่ $c$ ใดๆ ที่มีค่ามากกว่า 1. ในวิชานี้ ถ้าเราไม่ได้ระบุฐานของลอกการิทึม เราจะถือว่าเราใช้ลอกการิทึมฐานสอง.)

ถ้าในการค้นหาเราสามารถใช้การเปรียบเทียบได้เท่านั่น ตัวอย่างเช่น เราไม่สามารถจะพิจารณาชื่อที่เราต้องการเพื่อช่วยในการค้นหาได้ เราจะพบว่าเวลา $O(\log n)$ ที่ใช้ นั้น เป็นเวลาที่ดีที่สุดแล้ว. ทั้งนี้เนื่องจาก เมื่อการค้นหาสิ้นสุดลง ข้อมูลหนึ่งที่เราได้จากการค้นหาก็คือลำดับของข้อมูลอันนี้ในลำดับของรายชื่อ. เนื่องจากรายชื่อมีทั้งสิ้น $n$ ชื่อ การระบุตำแหน่งใดๆ ในลำดับนี้ ต้องใช้ข้อมูลขนาด $\log n$ บิต. ในการเปรียบเทียบแต่ละครั้ง เราได้ข้อมูลเพิ่มขึ้น 1 บิต ดังนั้น การจะ "เรียน" ตำแหน่งของข้อมูลโดยการเปรียบเทียบ เราต้องใช้การเปรียบเทียบทั้งสิ้นไม่น้อยกว่า $\log n$ ครั้ง.

การค้นหาแบบเทพยากรณ์

เราสามารถค้นหาคำตอบได้เร็วกว่านี้หรือไม่? สมมติว่าเรามีเทวดาอยู่ตนหนึ่งที่สามารถให้คำตอบได้ในเวลา $O(1)$ เมื่อเราถามคำถามไปว่า "รายชื่อนี้อยู่ที่หน้าใดของสมุดโทรศัพท์?" เราก็สามารถหาหมายเลขโทรศัพท์ของเขาได้ในเวลา $O(1)$ เช่นเดียวกัน. ในบางกรณี เราสามารถสร้างฟังก์ชั่นที่ทำหน้าที่แบบ "เทพยากรณ์" (Oracle) ได้. เราจะพูดถึงการค้นหาในรูปแบบนี้ เมื่อเราเรียนเรื่องของ hashing.

แล้วอะไรต่อไป?

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