মডিউল ১৭_৪ঃ Fibonacci Subproblem

আমরা আগের পার্টে fibonacci এর রিকারশান দেখেছি এবং সেটার ট্রি টা দেখেছি। এখন আমরা ট্রি টা আরেকটু ডিটেইলসে বোঝার চেষ্টা করবো।

এখানে একটি খেয়াল করে দেখো ৫ এর জন্য আমরা ৪ আর ৩ কে কল করছি। এবং ৪ এর জন্য ৩ আর ২ কে কল করছি। তাহলে এখানে ৩ দুইবার কল হচ্ছে একবার ৫ এর জন্য আরেকবার ৪ এর জন্য। ৪ এর জন্য যখন ৩ এর আন্সার আমরা পাই সেটা যদি আমরা সেভ করে রাখতে পারি তাহলে আমরা ৫ এর জন্য যে ৩ এর কল সেটাকে ইগ্নোর করতে পারতাম চাইলে।

উপরের ছবি অনুযায়ী যদি বলি তাহলে Sub problem1 এর আন্সার সলভ করে সেভ করে রাখলে subproblem 2 এর জন্য আমাদের আবার হিসেব করতে হচ্ছে না। তাহলে তখন এটা আমাদের কমপ্লেক্সিটিটা অনেক কমিয়ে দেয়। যদি আন্সার সেইভ না করে করি তাহলে কমপ্লেক্সিটি হয় O(2^n) আর সেইভ করে করলে হয় O(n)|