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

ความซับซ้อนเชิงเวลาของการหาค่าที่มากที่สุดในอาร์เรย์ที่ไม่เรียงลำดับซึ่งมีตัวเลข n ตัวคือเท่าใด

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

เวลาทำงานในกรณีเฉลี่ยอธิบายสิ่งใด

1. Aเวลาบนคอมพิวเตอร์ที่พบบ่อยที่สุด
2. Bเวลาคาดหมายภายใต้การแจกแจงของอินพุตขนาด n ที่กำหนด
3. Cเวลาสำหรับอินพุตที่มีความยาวเฉลี่ย
4. Dค่ากลางระหว่างเวลาทำงานในกรณีดีที่สุดกับกรณีเลวร้ายที่สุด

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

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

ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + O(n) มีผลเฉลยเป็น

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

อัลกอริทึมการเรียงลำดับใดเป็นแบบเสถียร (stable)

1. AHeap sort
2. BMerge sort
3. CSelection sort (แบบทั่วไป)
4. DQuicksort (แบบทำในที่เดิมทั่วไป)

ข้อใดเกี่ยวกับฟังก์ชันเรียกซ้ำที่ไม่มีกรณีฐานที่ไปถึงได้ถูกต้อง

1. Aคืนค่า 0 โดยอัตโนมัติ
2. Bคอมไพเลอร์แปลงเป็นลูปที่จบอย่างปลอดภัยเสมอ
3. Cทำงานในเวลา O(1)
4. Dเรียกตัวเองต่อไปจนสแต็กการเรียกล้น

เพื่อแสดงว่าปัญหาใหม่ X เป็น NP-hard คุณต้องทำอะไร

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

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

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