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

อัลกอริทึม O(n²) ใช้เวลา 1 วินาทีเมื่อ n = 1000 เมื่อ n = 2000 จะใช้เวลาประมาณเท่าใด

1. A2 วินาที
2. B4 วินาที
3. C1 วินาที
4. D8 วินาที

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

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

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

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

quicksort ใช้สมาชิกตัวแรกเป็นตัวหลักเสมอ อินพุตแบบใดแสดงพฤติกรรมกรณีเลวร้ายที่สุดของมัน

1. Aอาร์เรย์ที่เรียงแบบสุ่ม
2. Bอาร์เรย์ที่สมาชิกทุกตัวต่างกัน
3. Cอาร์เรย์ความยาว 2
4. Dอาร์เรย์ที่เรียงลำดับแล้ว

เหตุใดรูทีนการเรียงลำดับในไลบรารีจำนวนมากจึงเปลี่ยนไปใช้ insertion sort กับอาร์เรย์ย่อยที่เล็กมาก

1. AInsertion sort เป็น O(n log n) ในกรณีเลวร้ายที่สุด
2. BInsertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
3. CInsertion sort ใช้หน่วยความจำน้อยกว่าอัลกอริทึมการเรียงลำดับอื่นทุกตัวกับอินพุตใหญ่
4. Dอัลกอริทึมแบบเรียกซ้ำจัดการอาร์เรย์ที่เล็กกว่า 10 สมาชิกไม่ได้

ความซับซ้อนเชิงเวลาของการคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยตารางแบบล่างขึ้นบนคือเท่าใด

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

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

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

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

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