1.ง่าย
ความซับซ้อนเชิงเวลาของการค้นหาเชิงเส้นในอาร์เรย์ที่ไม่เรียงลำดับซึ่งมี n สมาชิก (กรณีเลวร้ายที่สุด) คือเท่าใด
- AO(log n)
- BO(n²)
- CO(1)
- DO(n)
ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย
2.ง่าย
การค้นหาแบบทวิภาคต้องการอะไรจากอินพุต
- Aอาร์เรย์ต้องมีแต่จำนวนบวก
- Bความยาวอาร์เรย์ต้องเป็นเลขกำลังสอง
- Cอาร์เรย์ต้องมีสมาชิกไม่เกิน 1000 ตัว
- Dอาร์เรย์ต้องเรียงลำดับแล้ว
3.ง่าย
ข้อใดเติบโตช้าที่สุดเมื่อ n มีค่ามาก
- AO(n log n)
- BO(log n)
- CO(n²)
- DO(n)
4.ปานกลาง
ความสัมพันธ์เวียนเกิด T(n) = T(n − 1) + O(n) มีผลเฉลยเป็นเท่าใด
- AO(n log n)
- BO(n²)
- CO(2ⁿ)
- DO(n)
5.ปานกลาง
อัลกอริทึมใดหาเส้นทางสั้นที่สุดจากต้นทางหนึ่งในกราฟที่น้ำหนักเส้นเชื่อมไม่เป็นลบ
- Aต้องใช้ Bellman–Ford ในทุกกรณี
- Bอัลกอริทึมของ Kruskal
- Cการค้นหาในแนวลึก
- Dอัลกอริทึมของ Dijkstra
6.ปานกลาง
การค้นหาในแนวกว้าง (BFS) บนกราฟที่ไม่มีน้ำหนักให้ผลเป็น
- Aต้นไม้ทอดข้ามที่น้อยที่สุด
- Bลำดับทอพอโลยีในทุกกราฟ
- Cเส้นทางสั้นที่สุดในกราฟที่มีเส้นเชื่อมน้ำหนักติดลบ
- Dเส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
7.ยาก
Insertion sort ทำงานใน O(n) บนอินพุตที่เรียงแล้ว สิ่งนี้ขัดกับขอบเขตล่าง Ω(n log n) ของการเรียงแบบเปรียบเทียบหรือไม่
- Aขัด แต่เฉพาะอาร์เรย์ที่สั้นกว่า 100
- Bไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต
- Cขัด ดังนั้นขอบเขตล่างจึงผิด
- Dไม่ขัด เพราะ insertion sort ไม่ใช่การเรียงแบบเปรียบเทียบ
8.ยาก
โดยใช้ทฤษฎีบทหลัก T(n) = 8T(n/2) + O(n²) มีผลเฉลยเป็น
- AΘ(n³)
- BΘ(n² log n)
- CΘ(n²)
- DΘ(n log n)
เฉลย
- 1. D · O(n)
- 2. D · อาร์เรย์ต้องเรียงลำดับแล้ว
- 3. B · O(log n)
- 4. B · O(n²)
- 5. D · อัลกอริทึมของ Dijkstra
- 6. D · เส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
- 7. B · ไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต
- 8. A · Θ(n³)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com