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

เรื่องสามเรื่องที่ไม่เกี่ยวกัน.
เรื่องที่หนึ่ง.
คุณคิดว่าซอฟต์แวร์ที่คุณใช้เกิดจากโปรแกรมกี่บรรทัด? (ยกตัวอย่างเช่น
ระบบปฏิบัติการ Linux หรือคอมไพเลอร์ภาษาซีของ gnu)
บางโปรแกรมนั้นยาวมากถึงระดับเป็นล้านบรรทัด!
คุณคิดว่าโปรแกรมเมอร์ทราบได้อย่างไรว่าโปรแกรมนั้นทำงานได้ถูกต้อง?
คุณคิดว่าทุกคนในทีมพัฒนาโปรแกรมได้อ่านซอร์สโค้ตทุกบรรทัดหรือ?
โปรแกรมเมอร์แต่่ละคน (หรืออาจจะมีคนเดียว?)
ไม่จำเป็นต้องเข้าใจรายละเอียดของโปรแกรมทุกจุด ทุกบรรทัด ในทุกๆ เวลา.
เขาสามารถจะมองโปรแกรมแยกเป็นส่วนๆ แยกกันเป็นหลายระดับ.
ในการทำความเข้าใจ หรือในการออกแบบนั้น
เขาไม่จำเป็นต้องลงไปพิจารณาในระดับของรายละเอียดปลีกย่อยทุกๆ ครั้ง.
ระดับของรายละเอียดที่เขามองนั้น
ก็จะขึ้นกับว่าในขณะนั้นเขากำลังทำอะไรอยู่. ยกตัวอย่างเช่น
ถ้าเขากำลังพิจารณาการทำงานของระบบติดต่อกับผู้ใช้
เขาไม่จำเป็นต้องไปคำนึงว่าโปรแกรมจะต้องทำอย่างไร
เพื่อที่จะวาดรูปเมาส์พอยน์เตอร์ให้เคลื่อนที่ไปได้ตามที่ผู้ใช้ขยับ
หรือว่าการกวาดลำแสงของจอภาพขณะนั้นทำงานได้อย่างไร.
เรื่องที่สอง.
ทำไมเราถึงมีรถยนต์ใช้? คำตอบง่ายๆ
ก็คือเพราะว่าเรารู้จักการใช้ล้อ เรารู้จักการสร้างเครื่องยนต์
การหล่อโลหะ ฯลฯ.
โลกของการคิดค้นเปลี่ยนหน้าตาไป เมื่อมนุษย์รู้จักการสร้างล้อที่หมุนได้
และรู้จักที่จะเปิดเผยให้ผู้อื่นมองเห็นว่าล้อมีลักษณะเช่นใด.
การค้นพบที่ ``ง่าย" และมีประโยชน์อย่างใหญ่หลวงได้มีคนทำไปหมดแล้ว: ล้อ
ไฟ ลูกตุ้มนาฬิกา เข็มทิศ ระบบการพิมพ์ หลอดไฟ สารกึ่งตัวนำ ทรานซิสเตอร์
คอมพิวเตอร์ เม้าส์ ระบบหน้าต่าง Linux ฯลฯ. (คำว่า ``ง่าย"
ที่ใช้ในที่นี้ไม่ได้ใช้เพื่อบอกว่าความพยายามที่ต้องใช้ก่อนที่จะค้นพบสิ่งเหล่านี้ไม่ได้มีอย่างมหาศาล.
คำว่าง่าย ใช้ในความหมายเดียวกับคำว่า ``simple"
ที่ตรงกันข้ามกับคำว่าซับซ้อน.)
แต่การที่ทุกคนไม่จำเป็นที่จะต้องเป็นนักคิดผู้ยิ่งใหญ่เพียงเพื่อจะได้มีแสงสว่างใช้ในเวลากลางคืนนั้น
เป็นการประหยัดเวลาและทรัพยากรของคนเราอย่างยิ่งยวด.
เรื่องที่สาม.
ทำไมตอนนี้เราจึงมีข้าวกินโดยไม่ต้องทำนา?
ทำไมเราถึงสามารถเดินทางไปไหนมาไหนได้โดยไม่จำเป็นต้องขับรถยนต์เป็น?
ทำไมเรามีเพลงฟังได้โดยไม่จำเป็นต้องเล่นดนตรีเป็น?
เมื่อสังคมได้พัฒนาผ่านสังคมยุคการเกษตรที่ทุกคนมีความสามารถจะกระทำกิจกรรมต่างๆ
ที่จำเป็นในการดำรงชีพได้ด้วยตนเอง ไปสู่สังคมที่ซับซ้อนขึ้น
สิ่งทีเกิดขึ้นก็คือความยุ่งยากในการจัดการกิจกรรมแต่ละส่วนของสังคม.
เราจัดการกับปัญหานี้โดยการกำหนดให้บุคคลบางคน
หรือบางกลุ่มไปมีหน้าที่ต้องเรียนรู้ และจัดการกับงานในส่วนนั้นๆ
ของสังคมโดยเฉพาะ. ด้วยเหตุนี้ผู้เชี่ยวชาญเฉพาะด้านก็เกิดขึ้น.
ผู้ยังไม่เชี่ยวชาญอย่างเราถึงได้มีสังคมที่ทำงานไปได้อาศัยอยู่
(โดยไม่รู้เลยว่าในแต่ละส่วนนั้นมันสามารถดำเนินไปได้อย่างไร).
แนวคิดหลักทั้งสาม: การมองปัญหาแบบภาพรวม (abstraction)
การใช้สิ่งที่คิดค้นมาแล้ว (reuse)
และการแบ่งงาน (division of labors)
เป็นฐานของการพัฒนาของอารยธรรมมนุษย์. เป้าหมายของมันก็คือ
การจัดการกับความซับซ้อน!!!
ในวิชานี้เราจะได้เข้าไปสัมผัสกับแนวคิดทั้งสามโดยผ่านการเรียนในห้อง
การทำการบ้าน และการทำโครงงาน.
ซอฟต์แวร์เป็นสิ่งที่ซับซ้อนที่สุดอย่างหนึ่งที่มนุษย์คิดค้นขึ้นมา.
แนวคิดมากมายได้ถูกนำมาปรับใช้
เพื่อลดความซับซ้อนของมันให้อยู่ในระดับที่มนุษย์ธรรมดาสามารถจัดการได้.
โครงสร้างข้อมูลพื้นฐานที่เราจะได้พบต่อๆ
ไปนั้นก็เหมือนกับเป็นระบบล้อที่เราสามารถนำไปใช้ได้เลย
เพียงแต่เราต้องมีความสามารถที่จะเลือกได้ว่าเราจะใช้อะไรที่ในจุดใด.
เราจะได้เรียนรู้วิธีมองปัญหาเป็นส่วนๆ เพื่อที่จะได้แบ่งงาน (ของตนเอง)
ในการจัดการกับปัญหาแต่ละอันได้โดยไม่ต้องพะวงกับส่วนอื่น ๆ.
ตัวอย่าง.
เราจะเริ่มจากตัวอย่างสองตัวอย่าง.
เกมสามมิติ.
วิธีการหนึ่งที่จะจำลองภาพที่ปรากฏต่อสายตาของผู้เล่นเกมก็คือการไล่วาดรูปของวัตถุต่างๆ
ทั้งหมด จากวัตถุที่อยู่ไกลจากสายตา ไล่ไปยังวัตถุที่อยู่ใกล้.
เนื่องจากเราวาดสิ่งที่อยู่ใกล้ทีหลัง
ภาพที่ปรากฏบนจอจึงมีลักษณะที่ซ้อนทับกันได้อย่างสวยงาม
และมีลักษณะเป็นสามมิติเหมือนกับภาพจริงๆ ที่เรามองเห็น.
แต่วิธีนี้มีการสิ้นเปลืองการประมวลผลมากโดยไม่จำเป็น ตัวอย่างเช่น
ในการวาดรูปนั้น
ถ้าเราทราบอยู่แล้วว่าวัตถุบางอันนั้นจะไม่อยู่ในขอบเขตของการมองเห็นอยู่แล้ว
เราก็ไม่จำเป็นต้องไปวาดมันลงไปบนจอ.
เพื่อความง่ายในการทำความเข้าใจ เราจะมองปัญหาในสองมิติ.
เรามีรูปเหลี่ยมมากมาย
แต่ในขณะหนึ่งเรามีมุมมองที่จำกัดอยู่ขอบเขตสี่เหลี่ยมอันหนึ่งเท่านั้น.
เราต้องการจะหาวัตถุทั้งหมดที่ปรากฏอยู่ในขอบเขตนั้น.
สมมติว่าเรามีวัตถุในฉากทั้งหมด <math>n</math> ชิ้น.
ถ้าเราต้องใช้เวลาในการตรวจสอบวัตถุทุกชิ้น เวลาที่เราจะต้องใช้
อย่างน้อยก็จะต้องแปรผันตรงกับจำนวนของวัตถุทั้งหมด. เราจะมีวิธีใดๆ
หรือไม่ ที่จะทำให้เราไม่ต้องไปพิจารณาวัตถุทั้งหมดโดยไม่จำเป็น?
สิ่งที่เราต้องการก็คือชุดของโปรแกรมย่อยที่จัดการกับข้อมูลของวัตถุที่
เมื่อเราบอกพิกัดของมุมมองไป
จะส่งรายการของวัตถุที่ปรากฏในมุมมองนั้นคืนกลับมา.
สังเกตว่าเมื่อเราได้กำหนดรูปแบบการติดต่อของโปรแกรมย่อยนั้นแล้ว
เราสามารถที่จะแบ่งงานไปให้กับผู้อื่นพัฒนาแทนได้. ยิ่งไปกว่านั้น
เราอาจจะเขียนโปรแกรมย่อยนั้นที่ทำงานได้
แต่ยังไม่จำเป็นต้องมีประสิทธิภาพเพียงพอที่เราต้องการขึ้นมาก่อน
เพื่อที่เราจะได้ทดสอบและพัฒนางานในส่วนอื่นไปก่อน.
เมื่อเราพร้อมก็สามารถจะกลับมาพัฒนาโปรแกรมย่อยในส่วนนี้ได้ต่อ.
เราจะแสดงวิธีการจัดการกับข้อมูลแบบหนึ่ง โดยใช้ตัวอย่างจากรูปต่อไปนี้.
โครงสร้างข้อมูลที่เราจะใช้เรียกว่า quad
tree. เนื่องจากมันมีลักษณะเป็นต้นไม้ที่เกิดจากการแบ่งพื้นที่ออกเป็นสี่ส่วน.
เริ่มต้นที่รูปดังกล่าว
เราจะแบ่งพื้นที่ออกเป็นสี่ส่วนโดยใช้เส้นแบ่งสองอัน (ดูรูปถัดไป).
เราจะพบว่าถ้ามุมมองของเราอยู่แค่ในส่วนหนึ่งส่วนใดของพื้นที่ทั้งสี่นี้แล้ว
(เช่นอยู่ในมุมบนขวา) ในการพิจารณาวัตถุต่างๆ
เราไม่จำเป็นที่จะต้องไปคำนึงถึงวัตถุที่ในมุมล่างซ้าย เป็นต้น.
เราอาจจะมีปัญหาอยู่บ้างสำหรับวัตถุที่อยู่ระหว่างเส้นแบ่ง
ซึ่งเราไม่สามารถจะจัดให้มันอยู่ในกลุ่มไหนได้
เราจึงต้องแยกวัตถุกลุ่มนี้เอาไว้ และไม่ว่ามุมมองของเราจะอยู่ที่จุดไหน
เราก็จะต้องตรวจสอบวัตถุในกลุ่มนี้เสมอ.
เมื่อเราได้การแบ่งในระดับที่หนึ่งแล้ว เราก็จะแบ่งพื้นที่สี่ส่วนย่อยๆ
นั้น ออกเป็นพื้นที่ย่อยๆ อีก. (เราทำได้ไม่ยากนั้น
โดยเราสามารถคิดว่าพื้นที่สี่ส่วนย่อยๆ นั้น เป็นเหมือนกับรูปวาดรูปแรก
และดำเนินการเช่นเดียวกับที่เราทำในตอนแรก.)
เราสามารถทำอย่างนี้ไปเรื่อยๆ จนกระทั่งในพื้นที่ต่างๆ ไม่เหลือวัตถุใดๆ
อีกแล้ว. รูปถัดไปแสดงตัวอย่างของการแบ่งพื้นที่ไปเรื่อยๆ. 
สังเกตว่าการแบ่งของเรามีลักษณะเป็นลำดับชั้น
โดยที่การแบ่งพื้นที่ครั้งแรกจะเป็นการแบ่งชั้นบนสุด.
จากนั้นก็จะเป็นการแบ่งที่ลำดับชั้นเล็กๆ ลงไป.
เมื่อเราได้การแบ่งทุกลำดับชั้นแล้ว เราสามารถจะสร้าง quad tree
สำหรับการค้นหาวัตถุที่อยู่ในมุมมองได้ดังรูปถัดไป.
ด้วยวิธีดังกล่าว เรา "คาดว่า"
เราน่าจะได้โครงสร้างข้อมูลที่ตอบปัญหาที่เราต้องการได้อย่างมีประสิทธิภาพ.
ปัญหาหนึ่งที่เราพบอยู่เสมอก็คือ
เราสามารถกล่าวได้ว่าแนวคิดนี้น่าจะมีประโยชน์
แต่เราไม่สามารถพิสูจน์อะไรได้เลย.
สำหรับโครงสร้างข้อมูลชนิดนี้ก็เช่นเดียวกัน
ทั้งนี้เนื่องจากถ้าการเรียงตัวของวัตถุไม่กระจายดีพอ
เราจะพบว่าการแบ่งพื้นที่เป็นส่วนๆ แบบนี้
ไม่ได้ลดเวลาในการค้นหาของเราลงเลย.
ในส่วนถัดไปเราจะแสดงตัวอย่างอื่นๆ
ของโครงสร้างข้อมูลที่เราสามารถกล่าวได้อย่างแน่ใจ
ถึงประสิทธิภาพของการประมวลผลของมัน. ในวิชานี้
เราจะมุ่งเน้นไปที่โครงสร้างข้อมูลในกลุ่มนี้.
การที่เราพิสูจน์ได้อย่างชัดเจนถึงประสิทธิภาพการทำงาน
จะทำให้เราเลือกใช้และปรับปรุงโครงสร้างข้อมูลเหล่านั้น
ให้ตรงกับความต้องการได้ง่ายขึ้น
สมุดโทรศัพท์.
เราสามารถมองสมุดโทรศัพท์เป็นโครงสร้างข้อมูลแบบหนึ่ง.
สิ่งที่สำคัญอย่างแรกที่เราต้องพิจารณาก็คือส่วนติดต่อ (interface)
ของโครงสร้างข้อมูล. สำหรับสมุดโทรศัพท์ สิ่งที่เรามีก็คือ
กระดาษเป็นหน้าๆ เราสามารถเปิดไปที่หน้าใดก็ได้
(โดยไม่จำเป็นต้องเปิดไปทีละหน้า) ในแต่ละหน้า
เราก็จะมีีรายชื่อของผู้ใช้โทรศัพท์ พร้อมกับเบอร์โทรศัพท์.
ที่ด้านหน้าเราจะมีสารบัญ (หรือดัชนี)
ที่ชี้เลขหน้าเริ่มต้นของรายชื่อที่ขึ้นต้นด้วยตัวอักษรต่างๆ.
ที่สำคัญที่สุดก็คือเราทราบว่า
รายชื่อในสมุดโทรศัพท์เรียงตามลำดับตัวอักษร.
ในส่วนนี้เราจะยกตัวอย่างวิธีการค้นเบอร์โทรศัพท์หลายๆ แบบ
และลองคิดคำนวนคร่าวๆ ว่าเวลาที่ใช้ในการค้นหาเป็นเท่าใด.
เราสมมติว่าเรามีรายชื่อในสมุดโทรศัพท์ทั้งสิ้น <math>n</math> รายชื่อ และ
(เพื่อความง่ายในการวิเคราะห์) ในแต่ละหน้า
เราสมมติว่าสามารถเก็บรายชื่อได้คนเดียว.
การค้นหาแบบตามลำดับ.
วิธีแรกของการหาเบอร์โทรศัพท์ก็คือการค้นโดยการเปิดจากหน้าแรกไปยังหน้าสุดท้าย.
การค้นหาแบบนี้อาจจะดูเหมือนไม่มีประสิทธิภาพ
แต่ในบางครั้งก็อาจจะเป็นสิ่งที่ดีที่สุดที่เราสามารถทำได้ก็ได้
ยกตัวอย่างเช่น ถ้าเราต้องการค้นหาหมายเลขโทรศัพท์จากนามสกุลของผู้ใช้เป็นต้น.
ถ้าชื่อของคนที่เราต้องการค้นหานั้นอยู่ในหน้าแรก
เวลาที่เราใช้ในการค้นหาก็จะมีค่าคงที่เสมอ
ไม่ว่าสมุดโทรศัพท์นั้นจะหนาเท่าใดก็ตาม.
ในทางกลับกันถ้าชื่อนั้นเป็นชื่อสุดท้าย
การค้นหาก็จะใช้เวลาเท่ากับเวลาที่ใช้ในการเปิดหน้ากระดาษ <math>n</math> ครั้ง.
เนื่องจากคนที่เปิดสมุดโทรศัพท์มีความเร็วในการเปิดในแต่ละหน้าไม่เท่ากัน
การที่เราจะกล่าวว่าเวลาที่ใช้คือ <math>n</math> วินาที ก็คงจะไม่ถูกต้องนัก.
แต่ถ้าเราลองพิจารณาว่า เราวิเคราะห์เวลาการทำงานไปทำไม
เราจะพบว่าเราวิเคราะห์ไปเพื่อความสะดวกในการเปรียบเทียบเวลาการทำงานของวิธีการหลายๆ
อัน และโดยปกติแล้ว เราต้องการทราบเวลาการทำงานคร่าวๆ
เมื่อข้อมูลมีเป็นจำนวนมาก.
ในที่นี้เราจะเขียนว่าวิธีการค้นหาแบบตามลำดับนั้น ใช้เวลา <math>O(n)</math>
ในการค้นหา. สัญลักษณ์ <math>O(\cdot)</math> (อ่านว่า Big-O)
นี้เป็นสัญลักษณ์ที่ใช้ระบุว่าฟังก์ชั่นที่เราพิจารณาอยู่นั้นมีพฤติกรรมเป็นเช่นใดเมื่อขนาดของ
$n$ มีค่ามากขึ้น. เราจะศึกษาเรื่องของโดยละเอียดต่อไปอีกครั้งหนึ่ง.
ในที่นี้ขอให้ผู้อ่านเข้าใจไปคร่าวๆ
ก่อนว่ามันคือวิธีการพิจารณาฟังก์ชั่นที่ไม่สนใจค่าคงที่
และค่าที่มีความสำคัญน้อยต่อการ "โต" ของฟังก์ชั่น.
สำหรับการค้นหาแบบนี้ ถ้าเป็นกรณีที่ดีที่สุดแล้ว เราจะใช้เวลา <math>O(1)</math>
นั่นคือ ใช้เวลาเป็นค่าคงที่. โดยทั่วไป
เราจะให้ความสำคัญมากกว่ากับเวลาที่ใช้ในกรณีที่แย่ที่สุด.
การค้นหาโดยใช้สารบัญและตามด้วยการหาแบบตามลำดับ.
เมื่อเราพิจารณาข้อมูลต่างๆ ที่สมุดโทรศัพท์มีเพื่อช่วยเราในการค้นหาแล้ว
เราจะพบว่า เราสามารถใช้สารบัญเพื่อหาชื่อที่ต้องการได้ง่ายขึ้น.
แต่ถ้าเรามองกรณีที่แย่ที่สุด
เราอาจจะพบว่ามันเป็นไปได้ที่ชื่อทุกชื่อจะมีตัวอักษรเริ่มต้นเหมือนกันหมด
ดังนั้น สารบัญที่เขียนขึ้นโดยใช้ตัวอักษรต้นเท่านั้น
ก็มิได้ช่วยให้เราค้นหาชื่อได้เร็วขึ้น นั่นคือเราก็ยังใช้เวลา <math>O(n)</math>
เท่าเดิม.
สิ่งที่เราต้องการจากสารบัญก็คือการแบ่งข้อมูลออกเป็นกลุ่มย่อยๆ
เพื่อลดเวลาในการค้นหาที่ไม่จำเป็นลง. ในที่นี้
ถ้าการสร้างสารบัญทำได้อย่างมีประสิทธิภาพ เราหวังว่า
ถ้าเราใช้สารบัญที่มีขนาด <math>r</math> เราจะใช้เวลาในการค้นชื่อ <math>O(n/r)</math>.
แต่การปรับปรุงนี้ก็ไม่ได้มาฟรีๆ เราต้องใช้เวลา <math>O(r)</math>
ในการค้นที่สารบัญอีก. ดังนั้นเวลาที่ใช้ทั้งหมดก็คือ <math>O(r+n/r)</math>.
เราสามารถกำหนดให้ <math>r=\sqrt{n}</math> เพื่อทำให้เวลาที่ใช้ทั้งเป็น
<math>O(\sqrt{n}+n/\sqrt{n})=O(\sqrt{n})</math> ซึ่งเร็วขึ้นกว่า <math>O(n)</math>
ที่เป็นเวลาที่ใช้ถ้าเราไม่ใช้สารบัญ (หรือใช้สารบัญที่ออกแบบไม่ดีพอ).
การค้นหาแบบทวิภาค.
คุณสมบัติอีกอันหนึ่งของสมุดโทรศัพท์ที่เรายังไม่ได้นำมาใช้
ก็คือการที่รายชื่อทั้งหมดถูกเรียงกันตามลำดับ. ดังนั้น
ถ้าเราเปิดดูรายชื่ออยู่ที่หน้าใดหน้าหนึ่ง เราสามารถบอกได้ทันทีว่า
ชื่อที่เราต้องการหานั้น อยู่ที่หน้าที่อยู่ก่อนหน้า
หรืออยู่หลังหน้าที่เรากำลังพิจารณาอยู่ โดยใช่้การเปรียบเทียบ. ดังนั้น
สิ่งที่เราทำได้ก็คือ เมื่อเริ่มต้น เราเปิดไปที่หน้ากลาง
จากนั้นพิจารณาว่ารายชื่อที่เราต้องการค้นหานั้น อยู่ที่ส่วนต้น
หรือส่วนปลายของสมุดโทรศัพท์. ในการเปรียบเทียบแต่ละครั้ง
เราลดขนาดของสมุดโทรศัพท์ลงครึ่งหนึ่ง. เราจะได้ว่า
ถ้าเราลดขนาดของสมุดโทรศัพท์ลงจนทำให้เราเหลือหน้ากระดาษแค่หนึ่งหน้า
เราก็จะได้คำตอบ. ถ้าเริ่มต้น เรามีสมุดโทรศัพท์จำนวน <math>n</math> หน้า
เราจะต้องเปรียบเทียบทั้งสิ้น <math>O(\log_2 n)</math> ครั้ง. (โดยทั่วไปแล้ว
เราสามารถละฐานของลอกการิทึม ได้ เนื่องจากเมื่อเราใช้เครื่องหมาย <math>O</math>
แล้ว <math>O(\log_{10} n)=O(\log_2 n)=O(\log_c n)</math> สำหรับค่าคงที่ <math>c</math> ใดๆ
ที่มีค่ามากกว่า 1. ในวิชานี้ ถ้าเราไม่ได้ระบุฐานของลอกการิทึม
เราจะถือว่าเราใช้ลอกการิทึมฐานสอง.)
ถ้าในการค้นหาเราสามารถใช้การเปรียบเทียบได้เท่านั่น ตัวอย่างเช่น
เราไม่สามารถจะพิจารณาชื่อที่เราต้องการเพื่อช่วยในการค้นหาได้
เราจะพบว่าเวลา <math>O(\log n)</math> ที่ใช้ นั้น เป็นเวลาที่ดีที่สุดแล้ว.
ทั้งนี้เนื่องจาก เมื่อการค้นหาสิ้นสุดลง
ข้อมูลหนึ่งที่เราได้จากการค้นหาก็คือลำดับของข้อมูลอันนี้ในลำดับของรายชื่อ.
เนื่องจากรายชื่อมีทั้งสิ้น <math>n</math> ชื่อ การระบุตำแหน่งใดๆ ในลำดับนี้
ต้องใช้ข้อมูลขนาด <math>\log n</math> บิต. ในการเปรียบเทียบแต่ละครั้ง
เราได้ข้อมูลเพิ่มขึ้น 1 บิต ดังนั้น การจะ "เรียน"
ตำแหน่งของข้อมูลโดยการเปรียบเทียบ
เราต้องใช้การเปรียบเทียบทั้งสิ้นไม่น้อยกว่า <math>\log n</math> ครั้ง.
การค้นหาแบบเทพยากรณ์.
เราสามารถค้นหาคำตอบได้เร็วกว่านี้หรือไม่?
สมมติว่าเรามีเทวดาอยู่ตนหนึ่งที่สามารถให้คำตอบได้ในเวลา <math>O(1)</math>
เมื่อเราถามคำถามไปว่า "รายชื่อนี้อยู่ที่หน้าใดของสมุดโทรศัพท์?"
เราก็สามารถหาหมายเลขโทรศัพท์ของเขาได้ในเวลา <math>O(1)</math> เช่นเดียวกัน.
ในบางกรณี เราสามารถสร้างฟังก์ชั่นที่ทำหน้าที่แบบ "เทพยากรณ์" (Oracle) ได้.
เราจะพูดถึงการค้นหาในรูปแบบนี้ เมื่อเราเรียนเรื่องของ hashing.
แล้วอะไรต่อไป?
เราจะได้เรียนโครงสร้างข้อมูลแบบต่างๆ
และจะได้ฝึกหัดเขียนและเลือกโครงสร้างข้อมูลเหล่านี้ไปใช้. และในขณะเดียวกัน
เราจะได้เรียนการวิเคราะห์เวลาการทำงานของโครงสร้างข้อมูลเหล่านี้
เพื่อที่เราจะได้สามารถเลือกใช้โครงสร้างข้อมูลได้อย่างเหมาะสม.