Fibonacci แบบ Recursion และ Memoization
Memoization เก็บผลลัพธ์ของ function call ก่อนหน้า
Fibonacci แบบ Recursion และ Memoization คืออะไร?
Memoization เก็บผลลัพธ์ของ function call ก่อนหน้า
หลีกเลี่ยงการคำนวณค่าเดิมซ้ำ
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
โค้ดตัวอย่าง
main.py
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))ผลลัพธ์ที่คาดหวัง
55หลักการทำงาน
Cache ลดเวลาจาก exponential เป็น O(n) โดยใช้หน่วยความจำ O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น