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

การค้นหาแบบทวิภาคต้องการอะไรจากอินพุต

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

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

1. A1 วินาที
2. B4 วินาที
3. C2 วินาที
4. D8 วินาที

ปัญหาหนึ่งมักถูกเรียกว่าจัดการได้ (tractable) ถ้า

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

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

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

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

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

ฟังก์ชันแฟกทอเรียลแบบเรียกซ้ำง่าย ๆ fact(n) = n × fact(n − 1) ใช้พื้นที่สแต็กเท่าใด

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

การเรียงลำดับทอพอโลยีทำได้เฉพาะกับ

1. Aกราฟมีทิศทางแบบไม่มีวงจร (DAG)
2. Bกราฟบริบูรณ์
3. Cกราฟไม่มีทิศทาง
4. Dกราฟที่มีน้ำหนักติดลบ

ปัญหาที่ตัดสินไม่ได้ (undecidable) ต่างจากปัญหาที่จัดการไม่ได้ (intractable) อย่างไร

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