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

ความซับซ้อนเชิงเวลาของการค้นหาในแนวลึก (DFS) บนกราฟที่เก็บเป็นรายการประชิดคือเท่าใด

1. AO(V × E)
2. BO(V²)
3. CO(V + E)
4. DO(E log V)

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

1. A9 วินาที
2. B12 วินาที
3. C6 วินาที
4. D3 วินาที

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

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

ข้อใดเกี่ยวกับฟังก์ชันเรียกซ้ำที่ไม่มีกรณีฐานที่ไปถึงได้ถูกต้อง

1. Aทำงานในเวลา O(1)
2. Bคอมไพเลอร์แปลงเป็นลูปที่จบอย่างปลอดภัยเสมอ
3. Cคืนค่า 0 โดยอัตโนมัติ
4. Dเรียกตัวเองต่อไปจนสแต็กการเรียกล้น

ความซับซ้อนเชิงเวลาของการคูณเมทริกซ์ n × n สองเมทริกซ์ด้วยลูปสามชั้นมาตรฐานคือเท่าใด

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

การค้นหาแบบทวิภาคต้องเปรียบเทียบประมาณกี่ครั้งในกรณีเลวร้ายที่สุดบนอาร์เรย์ที่เรียงแล้วซึ่งมี 1,000,000 สมาชิก

1. Aประมาณ 100
2. Bประมาณ 1,000
3. Cประมาณ 20
4. Dประมาณ 500,000

นิยามใดของคลาส P ถูกต้อง

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

ต้นทุนแบบกระจายของการเพิ่มค่าตัวนับฐานสองหนึ่งครั้งคือเท่าใด เมื่อการเพิ่มหนึ่งครั้งอาจพลิกหลายบิต

1. AO(1) ต่อการเพิ่มหนึ่งครั้ง
2. BO(n) ต่อการเพิ่มหนึ่งครั้ง
3. CO(log n) ต่อการเพิ่มหนึ่งครั้ง
4. DO(n log n) ต่อการเพิ่มหนึ่งครั้ง