Monday, April 4, 2011

Memoization

Not to be confused with memorization.

Memoization là một kỹ thuật tối ưu trong lập trình,Nó đổi không gian lưu trữ để giảm thời gian tính toán. Kỹ thuật này lưu trữ lại kết quả trả về của hàm và dùng lại vào lần gọi sau thay vì tính lại, bởi vậy sẽ tốn nhiều không gian nhớ hơn nhưng sẽ nhanh hơn.
Dùng khi viết hàm theo kiểu đệ qui.

VD: Ta có 5! = 120. Nếu muốn tính 6!, ta sẽ phải tính 6! = 6 * 5!.Thay vì tính lại 5!, ta lưu kết quả 5! đã tính trước đó (vào 1 mảng) rồi chỉ việc lấy giá trị của 5! ra nhân với 6.

......
Cache....

Memoization
Found this when solved PE74.


http://en.wikipedia.org/wiki/Memoization

No comments: