Longest Common Subsequence
การหาลำดับย่อยร่วมที่ยาวสุดเป็นอีกหนึ่งในปัญหาที่ถ้าเราเขียนตรงไปตรงมาแบบ recursive
จากการแบ่งการแก้ปัญหาใหญ่ด้วยคำตอบจากปัญหาย่อย ก็จะเกิดการซ้อนเหลื่อมของปัญหาย่อยเต็มไปหมด
(อ่านรายละเอียดในหนังสือ) แต่ถ้าเราใช้ dynamic programming ก็จะเร็วขึ้นมาก
ในกรณีของปัญหานี้ ประสิทธิภาพจะเปลี่ยนจาก O(2n) เป็น O(n2)
ขอเขียนให้ดู 3 แบบ แบบช้า (มีปัญหาย่อยซ้อนเหลื่อมกันมาก) แบบ top-down + memoization
และแบบ bottom-up dynamic programming
และทดลองกับข้อมูลสามแบบข้างล่างนี้ ลองพิจารณาดูว่าแต่ละแบบมีประสิทธิภาพเป็นเช่นไร
เมื่อทำงานกับข้อมูลในแต่ละแบบ ทำไมจึงเป็นเช่นนั้น?
ข้อมูลทั้งสองอาเรย์ต่างกัน
ข้อมูลเหมือนกันทั้งสองอาเรย์
ข้อมูลสุ่ม
สมชาย ประสิทธิ์จูตระกูล