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

ข้อใดเติบโตช้าที่สุดเมื่อ n มีค่ามาก

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

เวลาทำงานในกรณีเลวร้ายที่สุดของอัลกอริทึมอธิบายสิ่งใด

1. Aเวลาที่ใช้บนคอมพิวเตอร์ที่ช้า
2. Bเวลามากที่สุดที่ใช้ตลอดทุกอินพุตขนาด n
3. Cเวลาคาดหมายที่ใช้กับอินพุตสุ่มขนาด n
4. Dเวลาที่ใช้กับอินพุตที่เล็กที่สุด

การเข้าถึงสมาชิกในอาร์เรย์ด้วยดัชนีใช้เวลา

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

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

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

การวิเคราะห์แบบกระจายต้นทุน (amortised analysis) วัดสิ่งใด

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

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

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

เหตุใดการค้นหาเฉลี่ยในตารางแฮชจึงเป็น O(1) แต่กรณีเลวร้ายที่สุดเป็น O(n)

1. Aอาร์เรย์เข้าถึงใน O(n)
2. Bต้องเรียงคีย์ก่อน
3. Cคีย์จำนวนมากอาจชนกันไปอยู่ในถังเดียวกัน
4. Dฟังก์ชันแฮชช้า

ปัญหาการหยุด (halting problem) แสดงว่า

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