บทที่ 18 ความซับซ้อนของเวลา
จบบทนี้ น้องจะอ่านขอบเขตในโจทย์ เช่น 1 ≤ N ≤ 100000 แล้วบอกได้ก่อนเขียนโค้ดว่าวิธีไหนทันเวลา วิธีไหนไม่ทัน และหน่วยความจำพอไหม เป็นทักษะที่ใช้ในทุกโจทย์ของช่วงอัลกอริทึมต่อจากนี้ เพราะโจทย์ระดับค่าย 2 มักตั้งขอบเขตไว้ให้วิธีตรงไปตรงมาไม่ทัน บทนี้ใช้ภาษา C++ กับ STL จากบทที่ 15 ถึง 17 และอ้างเวลาที่วัดไว้ในหน้า 4.5 กับ 13.3 อยู่บ่อยๆ
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 18.1 นับการทำงานและ Big O | นับว่าโปรแกรมทำงานกี่ครั้งในกรณีแย่ที่สุด ตัดค่าคงที่และพจน์เล็กจนเหลือ Big O และรู้ว่าแต่ละแบบโตเร็วแค่ไหน |
| 18.2 ขอบเขตโจทย์กับเวลาจริง | เวลาจริงของงานแต่ละแบบ ตารางขอบเขต N กับวิธีที่ทัน และเวลาที่หายไปกับการอ่านเขียนข้อมูล |
| 18.3 วิเคราะห์ลูปและ recursion | บอก Big O ของลูปซ้อน ลูปคูณสอง และ recursion จากโครงของโค้ด |
| 18.4 STL และหน่วยความจำ | เวลาของคำสั่ง vector queue string กับดัก erase หัวแถว และคำนวณขนาดอาเรย์เทียบลิมิต 256 MB |
| 18.5 ลดความซับซ้อนและสองตัวชี้ | แก้โจทย์เดียวกันจาก O(N3) เป็น O(N) และใช้สองตัวชี้หาช่วงที่ยาวที่สุด |