1.ง่าย
เวลาทำงานในข้อใดเป็นพหุนาม
- AO(n!)
- BO(2ⁿ)
- CO(n³)
- DO(nⁿ)
ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย
2.ง่าย
การค้นหาแบบทวิภาคต้องการอะไรจากอินพุต
- Aอาร์เรย์ต้องมีสมาชิกไม่เกิน 1000 ตัว
- Bอาร์เรย์ต้องมีแต่จำนวนบวก
- Cอาร์เรย์ต้องเรียงลำดับแล้ว
- Dความยาวอาร์เรย์ต้องเป็นเลขกำลังสอง
3.ง่าย
อัลกอริทึม O(n²) ใช้เวลา 1 วินาทีเมื่อ n = 1000 เมื่อ n = 2000 จะใช้เวลาประมาณเท่าใด
- A8 วินาที
- B2 วินาที
- C4 วินาที
- D1 วินาที
4.ปานกลาง
ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + O(n) มีผลเฉลยเป็น
- AO(n log n)
- BO(n)
- CO(log n)
- DO(n²)
5.ปานกลาง
ด้วยเหรียญ 1, 3 และ 4 และยอด 6 วิธีละโมบ "หยิบเหรียญใหญ่สุดก่อน" ใช้เหรียญกี่เหรียญเมื่อเทียบกับค่าที่เหมาะสมที่สุด
- Aละโมบใช้ 2 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
- Bละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
- Cละโมบใช้ 4 เหรียญ ค่าที่เหมาะสมที่สุดคือ 3
- Dละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 3
6.ปานกลาง
ความสัมพันธ์เวียนเกิด T(n) = T(n/2) + O(1) มีผลเฉลยเป็นเท่าใด
- AO(n log n)
- BO(n)
- CO(log n)
- DO(1)
7.ยาก
ทฤษฎีบท Cook–Levin พิสูจน์สิ่งใด
- Aปัญหาการหยุดตัดสินไม่ได้
- BP ไม่เท่ากับ NP
- Cปัญหาความสอดคล้องของสูตรบูลีน (SAT) เป็น NP-complete
- Dทุกปัญหา NP แก้ได้ในเวลาเอกซ์โพเนนเชียล
8.ยาก
เส้นทางง่ายที่สั้นที่สุดหาได้ในเวลาพหุนาม สิ่งใดที่ทราบเกี่ยวกับการหาเส้นทางง่ายที่ยาวที่สุดระหว่างสองจุดยอดในกราฟทั่วไป
- Aแก้ได้ด้วยอัลกอริทึมของ Dijkstra โดยกลับเครื่องหมายน้ำหนัก
- Bเป็น NP-hard
- Cตัดสินไม่ได้
- Dแก้ได้ใน O(V + E) เสมอ
เฉลย
- 1. C · O(n³)
- 2. C · อาร์เรย์ต้องเรียงลำดับแล้ว
- 3. C · 4 วินาที
- 4. A · O(n log n)
- 5. B · ละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
- 6. C · O(log n)
- 7. C · ปัญหาความสอดคล้องของสูตรบูลีน (SAT) เป็น NP-complete
- 8. B · เป็น NP-hard
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com