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

ความซับซ้อนเชิงเวลาของการค้นหาแบบทวิภาค (binary search) บนอาร์เรย์ที่เรียงลำดับแล้วคือเท่าใด

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

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

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

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

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

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

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

ฟังก์ชันแฟกทอเรียลแบบเรียกซ้ำง่าย ๆ fact(n) = n × fact(n − 1) ใช้พื้นที่สแต็กเท่าใด

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

เหตุใดจึงมักละฐานของลอการิทึมใน Big O เช่น O(log n)

1. Aลอการิทึมที่ฐานต่างกันต่างกันเพียงตัวคูณคงที่
2. Bลอการิทึมทั้งหมดในวิทยาการคอมพิวเตอร์มีฐาน 10 จึงไม่ต้องระบุ
3. Cฐานมีความสำคัญเฉพาะเมื่อ n น้อย
4. Dลอการิทึมถูกปัดเป็นจำนวนเต็มเสมอ

การคูณแบบ Karatsuba ตรงตาม T(n) = 3T(n/2) + O(n) ผลเฉลยคืออะไร

1. AΘ(n^{log₂ 3}) ประมาณ n^1.585
2. BΘ(n log n)
3. CΘ(n³)
4. DΘ(n²)

n! และ 2ⁿ เปรียบเทียบกันอย่างไรเมื่อ n มาก

1. A2ⁿ เติบโตเร็วกว่า n!
2. Bn! เป็น O(n²)
3. Cเติบโตในอัตราเดียวกัน
4. Dn! เติบโตเร็วกว่า 2ⁿ