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)
สมชาย ประสิทธิ์จูตระกูล