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