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

การเติบโตแบบ O(2ⁿ) เรียกว่าอะไร

1. Aพหุนาม
2. Bเชิงเส้น
3. Cลอการิทึม
4. Dเอกซ์โพเนนเชียล

counting sort สำหรับจำนวนเต็ม n ตัวในช่วง 0 ถึง k ใช้เวลาเท่าใด

1. AO(n log n)
2. BO(k log n)
3. CO(n + k)
4. DO(n²)

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

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

การที่ปัญหามีโครงสร้างย่อยเหมาะสมที่สุด (optimal substructure) หมายความว่าอย่างไร

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

ความซับซ้อนเชิงเวลาเฉลี่ยแบบกระจายต้นทุน (amortised) ของการต่อท้ายอาร์เรย์พลวัตที่เพิ่มความจุเป็นสองเท่าเมื่อเต็มคือเท่าใด

1. AO(log n)
2. BO(n)
3. CO(1)
4. DO(n²)

ความซับซ้อนเชิงเวลาของฟีโบนักชีแบบเรียกซ้ำตรง ๆ (fib(n) = fib(n−1) + fib(n−2)) คือ

1. Aเอกซ์โพเนนเชียล
2. Bคงที่
3. Cลอการิทึม
4. Dเชิงเส้น

การเลือกปลายทั้งสองของทุกเส้นเชื่อมใน maximal matching ให้ผลเป็นเซตครอบคลุมจุดยอด (vertex cover) เซตครอบคลุมนี้ดีเพียงใด

1. Aเป็นเซตครอบคลุมจุดยอดที่เล็กที่สุดเสมอ
2. Bขนาดไม่เกินสองเท่าของเซตครอบคลุมจุดยอดที่เล็กที่สุด
3. Cไม่เกิน log n เท่าของค่าต่ำสุด
4. Dไม่ทราบคุณภาพเมื่อเทียบกับค่าที่เหมาะสมที่สุด

นิยามใดของคลาส NP ถูกต้อง

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