Fibonacci Numbers

เราเขียนโปรแกรมหาเลขฟิโบนักชชีได้ง่าย ๆ ตรงไปตรงมาจาก recurrence f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1 ได้ผลดังแสดงข้างล่างนี้

Overlapping Subproblems

ลองเลือกทุกบรรทัดและเลือกให้ Σ(lines) ด้วย เพื่อแสดงรวมภาระทั้งหมด จากนั้นลองเลือกให้แสดงเวลาการทำงาน (times) ลองตั้ง f(n,c) = c/Math.pow(1.6,n) ลอง c/Math.pow(2,n) และลอง c/Math.pow(1.618,n) เดาสิว่าประสิทธิภาพเป็นฟังก์ชันอะไร ?

Memoization & Dynamic Programming

เนื่องจากการเขียนแบบบนมี overlapping subproblems เราจึงแก้ปัญหาได้ด้วย memoization และเปลี่ยนเป็นวงวนแบบ dynamic programming ได้ ดังแสดงและเปรียบเทียบกับแบบแรก เห็นได้ว่า เวลาการทำงานต่างกันลี้ลับ ลองไม่เลือกบรรทัดที่เรียก fib(n) จะได้เห็นผลการทดลองของแบบที่เหลือ ทั้งแบบ memoization และแบบ dynamic prog. ใช้เวลาเป็นเชิงเส้นทั้งคู่ แต่มีความชันต่างกัน นอกจากนี้ เรายังเขียนอีกแบบด้วยเทคนิคการยกกำลังที่เขียนแบบ divide and conquer ทำให้การยกกำลัง n ใช้เวลาแปรตาม log n (ลองพิจารณาเองว่า แบบหลังนี้หาจำนวนฟิโบนักชีได้อย่างไร)

Linear and Log

การทดลองนี้ต้องการเน้นเฉพาะสองวิธีหลัง เพื่อให้เห็นว่าแบบยกกำลังนั้น มีภาระการทำงานน้อยกว่าแบบ dynamic programming ลองหาสาเหตุสิว่า ทำไมเส้นของแบบหลังจึงมีลักษณะซิกแซกตามที่เห็น (แต่มีแนวโน้มการเติบโตแบบ log)


สมชาย ประสิทธิ์จูตระกูล