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

ความซับซ้อนเชิงพื้นที่ (space complexity) วัดสิ่งใด

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

ความซับซ้อนเชิงเวลาในกรณีดีที่สุดของ insertion sort บนอาร์เรย์ที่เรียงแล้วคือเท่าใด

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

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

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

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

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

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

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

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

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

ปัญหาพนักงานขายเดินทางถูกจัดประเภทอย่างไร

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

2²ⁿ อยู่ใน O(2ⁿ) หรือไม่

1. Aไม่ เพราะ 2²ⁿ เติบโตช้ากว่า 2ⁿ
2. Bใช่ เพราะตัวคูณคงที่ในเลขชี้กำลังถูกละไว้เสมอใน Big O
3. Cใช่ เพราะทั้งสองเป็นเอกซ์โพเนนเชียล
4. Dไม่ เพราะ 2²ⁿ = 4ⁿ และ 4ⁿ / 2ⁿ = 2ⁿ เติบโตไม่มีขอบเขต