Fibonacci Number Sequence Algorithm

Fibonacci เป็นลำดับรูปแบบหนึ่งที่น่าสนใจ โดยมีรูปแบบของลำดับดังนี้

fibo(0) = 0

fibo(1) = 1

fibo(2) = 1

fibo(3) = 2

fibo(4) = 3

fibo(5) = 5

....

...

..

.

fibo(N) = fibo(N - 1) + fibo(N - 2)

และ Fibonacci ก็ยังเป็นโจทย์พื้นฐานการเขียนโปรแกรมที่ได้รับความนิยมอีกด้วย ...
ผมว่าทุกคนเห็นโครงสร้างของลำดับที่ผมให้มา ก็อาจจะเขียนโปรแกรมหา Fibonacci ลำดับนี้ N ได้ดังนี้

Speed == Exponential == O(2^n)

แต่ Algorithm นี้มีปัญหาแน่ๆ ... เพราะว่าถ้าเราลอง Proof ที่ N = 5 เราจะเขียนการเรียก Recursive Function ได้ดังนี้

เราจะเห็นว่ามีการคำนวณซ้ำๆ เยอะมาก ... นี่แค่ N = 5 ...
ลองจินตนาการ N สัก 50 สิ (เอ่อม ไม่มีปัญญาเขียน) คงจะเยอะน่าดู
ลองรันดูก็ได้ ผมว่าใส่สัก 75 ก็ขี้เกียจรอแล้ว ...

แล้วอะไรที่ดีกว่า ? เราจะเห็นว่าในเมื่อมีการคำนวณซ้ำๆ
ทำไมถึงไม่คำนวณรอบเดียวก็พอ หรือคำนวณไว้ก่อนแล้วเก็บค่ามาใช้

วิธีการนั้นเรียกว่า Dynamic Programming
วิธีการนี้จะให้เราสร้างตารางจำลองขึ้นมาเก็บข้อมูลที่คำนวณได้แล้วหยิบมาใช้

Speed == Linear == O(n)

แบ่งเป็น 2 แบบคือ Bottom-up และ Top-Down (ผมอธิบายตามความเข้าใจนะ)

แบบ Bottom-up จะคำนวณค่าใส่ตารางไปจนถึงตัว N แล้วหยิบตัว N มาให้เรา ดังนั้นความเร็วของ Algorithm นี้คือ O(N) ดังนั้นถ้าในปัญหาที่บอกว่า "ต้องการ Fibonacci ตัวที่ 1 - N จะมีการใช้ตารางทั้งหมด N ตารางในการคำนวณ ก็เลยช้ากว่าแบบ Top-Down" แต่ข้อดีก็คือเราสามารถคำนวณ "Fibonacci ตัวที่ N ใดๆ ก็ได้"

แบบ Top-Down จะเป็นการคำนวณค่าเก็บลงตารางหลักเพียงตารางเดียว แล้วคำนวณตัวต่อๆ ไปจากตัวก่อนหน้าที่คำนวณได้ แต่แบบนี้จะมีข้อจำกัดคือ "เราไม่สามารถขอตัว N ได้ ถ้าเรายังไม่ได้คำนวณตัวที่ (N - 1) และ (N - 2)"  

แต่เนื่องจาก C/C++ ไม่มี BigInteger Library ให้ใช้
การทดสอบแค่ N = 100 ก็เกินค่า Integer 64 bit แล้ว (long long)
ผมก็เลยต้องไปทดสอบกับภาษาอื่น ซึ่งผมเลือก Ruby ที่มี BigNum

ซึ่งโจทย์ที่ผมทำการทดสอบคือ "พิมพ์ลำดับ Fibonacci ตั้งแต่ 1 - N"
ทดสอบเล่นๆ 3000 อันดับ ได้ผลลัพธ์ดังนี้

Bottom-up Dynamic Programming

Top-down Dynamic Programming 

ทดสอบกันอีกสักหน่อย ว่าลำดับ Fibonacci ที่ 100000 จะใช้เวลาเท่าไหร่ถ้าเราใช้แบบ Bottom-up
แน่นอนว่าแบบ Top-Down ทำไม่ได้ (ทำได้ต่อเมื่อขอตัวที่ 1 - 100000) ซึ่งขี้เกียจรอ :P

เลขยาวมากกกกก ~ ใช้เวลาไป 0.6 วินาที
References --> http://www.algorithmist.com/index.php/Dynamic_Programming

ยังมี Algorithm ที่เป็น O(logN) สำหรับการหา Fibonacci ด้วย เป็นวิธี Divide and Conquer ที่นำเอา Matrix เข้ามาช่วย โดยสูตรจะเป็นไปตามนี้ครับ

พอมาเขียนใน Ruby ก็จะได้แบบนี้ครับ

มาทดสอบ Algorithm นี้กัน ว่าจะเร็วแค่ไหนด้วยโจทย์เดิม
โจทย์แรก พิมพ์ลำดับ Fibonacci ลำดับที่ 1 - 3000

เร็วกว่าแบบ Bottom-up แต่ช้ากว่าแบบ Top-Down นิดหน่อย

โจทย์สอง พิมพ์ค่าเลข Fibonacci ลำดับที่ 100000

เร็วกว่าแบบ Bottom-up มหาศาล เพราะใช้การคำนวณล้วนๆ ไม่ต้องเสียเวลาในกรสร้างพื้นที่เก็บข้อมูล

** ขอบคุณอาจารย์ปรีชา สำหรับ Algorithm ด้วยครับ :)