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

อัลกอริทึมกำลังเดรัจฉาน (brute force) คืออะไร

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

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

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

เวลาทำงานในข้อใดเป็นพหุนาม

1. AO(nⁿ)
2. BO(2ⁿ)
3. CO(n³)
4. DO(n!)

การกล่าวว่าอัลกอริทึม O(n²) เป็น O(n³) ด้วย ถูกต้องหรือไม่

1. Aถูกต้อง เพราะ Big O เป็นขอบเขตบน และ n² เติบโตไม่เร็วกว่า n³
2. Bถูกต้อง แต่เฉพาะเมื่อ n น้อยกว่า 100
3. Cไม่ถูก เพราะ n³ น้อยกว่า n² เมื่อ n มาก
4. Dไม่ถูก เพราะ Big O ต้องระบุอัตราการเติบโตที่แน่นอนของฟังก์ชันเสมอ

การเรียกซ้ำของ merge sort สำหรับอาร์เรย์ n สมาชิกมีกี่ระดับ

1. Aประมาณ log₂ n
2. Bประมาณ n
3. Cประมาณ n / 2
4. Dประมาณ √n

คุณเรียงอาร์เรย์ n สมาชิกหนึ่งครั้ง แล้วตอบคำถามการเป็นสมาชิก k ข้อด้วยการค้นหาแบบทวิภาค ต้นทุนรวมเท่าใด

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

Insertion sort ทำงานใน O(n) บนอินพุตที่เรียงแล้ว สิ่งนี้ขัดกับขอบเขตล่าง Ω(n log n) ของการเรียงแบบเปรียบเทียบหรือไม่

1. Aไม่ขัด เพราะ insertion sort ไม่ใช่การเรียงแบบเปรียบเทียบ
2. Bไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต
3. Cขัด ดังนั้นขอบเขตล่างจึงผิด
4. Dขัด แต่เฉพาะอาร์เรย์ที่สั้นกว่า 100

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

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