1.ง่าย
อัลกอริทึมที่มีลูปซ้อนกันสองชั้น แต่ละชั้นทำงาน n รอบ โดยทั่วไปมีความซับซ้อนเท่าใด
- AO(log n)
- BO(n²)
- CO(2n)
- DO(n)
ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย
2.ง่าย
อัลกอริทึม O(n²) ใช้เวลา 1 วินาทีเมื่อ n = 1000 เมื่อ n = 2000 จะใช้เวลาประมาณเท่าใด
- A8 วินาที
- B4 วินาที
- C1 วินาที
- D2 วินาที
3.ง่าย
ความซับซ้อนเชิงพื้นที่ (space complexity) วัดสิ่งใด
- Aปริมาณหน่วยความจำที่อัลกอริทึมต้องใช้เมื่ออินพุตใหญ่ขึ้น
- Bขนาดทางกายภาพของคอมพิวเตอร์
- Cจำนวนบรรทัดของโค้ด
- Dพื้นที่ดิสก์ของไฟล์โปรแกรมหลังจากคอมไพล์แล้ว
4.ปานกลาง
การค้นหาในแนวกว้าง (BFS) บนกราฟที่ไม่มีน้ำหนักให้ผลเป็น
- Aลำดับทอพอโลยีในทุกกราฟ
- Bเส้นทางสั้นที่สุดในกราฟที่มีเส้นเชื่อมน้ำหนักติดลบ
- Cเส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
- Dต้นไม้ทอดข้ามที่น้อยที่สุด
5.ปานกลาง
ความซับซ้อนเชิงเวลาของการคูณเมทริกซ์ n × n สองเมทริกซ์ด้วยลูปสามชั้นมาตรฐานคือเท่าใด
- AO(n²)
- BO(n² log n)
- CO(n)
- DO(n³)
6.ปานกลาง
เหตุใดการโปรแกรมพลวัตจึงไม่ช่วยเร่ง merge sort ได้จริง
- Aปัญหาย่อยของมันไม่ซ้อนทับกัน จึงไม่มีอะไรให้ใช้ซ้ำ
- BMerge sort เป็น O(n) อยู่แล้ว
- Cการโปรแกรมพลวัตใช้ได้กับปัญหากราฟเท่านั้น ไม่ใช่กับอาร์เรย์
- DMerge sort ไม่มีโครงสร้างแบบเรียกซ้ำ
7.ยาก
เพื่อแสดงว่าปัญหาใหม่ X เป็น NP-hard คุณต้องทำอะไร
- Aลดรูปปัญหา NP-hard ที่ทราบมาเป็น X ในเวลาพหุนาม
- Bแสดงว่า X ไม่มีอัลกอริทึมพหุนามสำหรับอินพุตเล็ก
- Cลดรูป X ไปเป็นปัญหา NP-hard ที่ทราบในเวลาพหุนาม
- Dแสดงว่า X ตรวจสอบได้ในเวลาพหุนาม
8.ยาก
การเรียงลำดับทอพอโลยีทำได้เฉพาะกับ
- Aกราฟที่มีน้ำหนักติดลบ
- Bกราฟมีทิศทางแบบไม่มีวงจร (DAG)
- Cกราฟไม่มีทิศทาง
- Dกราฟบริบูรณ์
เฉลย
- 1. B · O(n²)
- 2. B · 4 วินาที
- 3. A · ปริมาณหน่วยความจำที่อัลกอริทึมต้องใช้เมื่ออินพุตใหญ่ขึ้น
- 4. C · เส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
- 5. D · O(n³)
- 6. A · ปัญหาย่อยของมันไม่ซ้อนทับกัน จึงไม่มีอะไรให้ใช้ซ้ำ
- 7. A · ลดรูปปัญหา NP-hard ที่ทราบมาเป็น X ในเวลาพหุนาม
- 8. B · กราฟมีทิศทางแบบไม่มีวงจร (DAG)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com