ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย

สัญกรณ์ใดใช้อธิบายขอบเขตบนของอัตราการเติบโต

1. ALittle omega
2. BBig Omega
3. CBig Theta
4. DBig O

สัญกรณ์ใดใช้อธิบายขอบเขตล่างของอัตราการเติบโต

1. AΘ (Big Theta)
2. BΩ (Big Omega)
3. Co (little o)
4. DO (Big O)

ความซับซ้อนเชิงเวลาของการค้นหาในแนวลึก (DFS) บนกราฟที่เก็บเป็นรายการประชิดคือเท่าใด

1. AO(E log V)
2. BO(V + E)
3. CO(V²)
4. DO(V × E)

ความซับซ้อนเชิงเวลาของอัลกอริทึม Bellman–Ford บนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด

1. AO(V × E)
2. BO(V³ × E)
3. CO(V + E)
4. DO(E log V)

อัลกอริทึมใดหาเส้นทางสั้นที่สุดจากต้นทางหนึ่งในกราฟที่น้ำหนักเส้นเชื่อมไม่เป็นลบ

1. Aการค้นหาในแนวลึก
2. Bอัลกอริทึมของ Kruskal
3. Cต้องใช้ Bellman–Ford ในทุกกรณี
4. Dอัลกอริทึมของ Dijkstra

การโปรแกรมพลวัต (dynamic programming) มีประโยชน์เมื่อปัญหามี

1. Aลูปเพียงชั้นเดียว
2. Bอินพุตสุ่มเท่านั้น
3. Cไม่มีปัญหาย่อยเลย จึงแก้ได้ในขั้นตอนเดียว
4. Dปัญหาย่อยที่ซ้อนทับกันและโครงสร้างย่อยเหมาะสมที่สุด

ขอบเขตใดถูกต้องสำหรับ log(n!)

1. AΘ(n log n)
2. BΘ(n)
3. CΘ(n²)
4. DΘ(log n)

ปัญหาหนึ่งเป็น NP-complete ถ้ามัน

1. Aอยู่นอก NP แต่ยากกว่าทุกปัญหา NP เช่น ปัญหาการหยุด
2. Bแก้ได้ในเวลาพหุนาม
3. Cแก้ไม่ได้เลย
4. Dอยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม