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

memoisation คืออะไร

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

อัลกอริทึมการเรียงลำดับใดเลือกตัวหลักแล้วแบ่งอาร์เรย์เป็นสมาชิกที่เล็กกว่าและใหญ่กว่า

1. AMerge sort
2. BQuicksort
3. CBubble sort
4. DInsertion sort

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

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

ความซับซ้อนเชิงเวลาเฉลี่ยแบบกระจายต้นทุน (amortised) ของการต่อท้ายอาร์เรย์พลวัตที่เพิ่มความจุเป็นสองเท่าเมื่อเต็มคือเท่าใด

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

อัลกอริทึม Floyd–Warshall คำนวณอะไรและเร็วเพียงใด

1. Aเส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)
2. Bเส้นทางสั้นที่สุดจากจุดยอดต้นทางหนึ่งไปยังจุดยอดอื่นทั้งหมดใน O(V + E)
3. Cต้นไม้ทอดข้ามที่น้อยที่สุดใน O(E log V)
4. Dลำดับทอพอโลยีใน O(V²)

ความซับซ้อนเชิงเวลาของอัลกอริทึมการโปรแกรมพลวัตมาตรฐานสำหรับสายอักขระย่อยร่วมที่ยาวที่สุด (LCS) ของสายอักขระที่ยาว m และ n คือเท่าใด

1. AO(2^m+n)
2. BO(mn log n)
3. CO(m + n)
4. DO(mn)

ปัญหาความสอดคล้องข้อใดต่อไปนี้ทราบว่าแก้ได้ในเวลาพหุนาม

1. A2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
2. BSAT ทั่วไปบนสูตรรูปแบบนอร์มัลเชิงเชื่อม
3. C3-SAT ซึ่งแต่ละวลีมีลิเทอรัลสามตัวพอดี
4. Dความสอดคล้องของวงจร

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

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