Dinamik Programlama'da Hatırlama Metodu

Dinamik Programlama'da Hatırlama Metodu

Dinamik programlama bize her hangi bir problemin çözümünde klasik olarak kullandığımız algoritmalardan daha etkili algoritmalar oluşturmamızı sağlar.Memorize,Bottom-Up gibi bir çok yöntemle algoritmalarımızı geliştirebiliriz.Ben bu anlatımda Hatırlama* (Remember) yöntemini kullanarak fibonacci sayılarının nasıl daha etkili hesaplanabileceğini anlatacağım.

Öncelikkle bazı temel mantık öğelerini ve klasik algoritmamızın çalışma zamanından başlayalım;

F(1)=F(2) = 1

F(n) = F(n-1) + F(n-2) bu formüller fibonacci serisinin formülleştirilmiş halidir.

T(n) ise T (n-1)+ T(n-2) + O(1) e eşittir.Klasik impelementasonumuza bakarsak

Fib(n):

if n<=2 : f =1

else : f = fib(n-1) + fib(n-2)

return f

Yukarıdaki çözüm recursive şeklinde fibonacci sayılarının hesaplanmasını sağlayan algoritma.Biz bu algoritmayı çalıştırdığımızda programımız aşşağıdaki ağacın kollarındaki tüm elemanları hesaplayarak kökde duran sonucu bulmaya çalışıyor.

Görev ağacına baktığımızda aslında bazı değeri zaten önceden hesapladığınızı üst seviyeye geçerken boş yere aynı değeri hesapladığımızı görmüşsünüzdür hatta kökün sağındaki koldaki n-2 değerinin diğer sol kolun bir alt seviyesinde hesaplandığını görülüyor ,o halde bizim komple o sağ kolu hesaplamamız gereksiz.Peki bundan nasıl kurtulacağız ? Hatırlayarak ! . Her hesapladığımız değeri bir key-value sisteminde(programlama dillerine göre değişir) saklayarak boş hesaplamalardan kurtuluyoruz.Örneklemek gerekirse aşşağıdaki kodla ;

memo = {}

Fib(n):

   if n in memo return memo[n]

   if n<=2 : f=1

   else : f = Fib(n-1) + Fib(n-2)

   memo[n] = f

   return f

Peki bu çözümümüzün T(n)'ı kaça eşit derseniz .

Zaman = parçalanmış çözümler * zaman/parçalanmış çözümler zaman = zaman ? Yani yukarıdaki T(n-1)+T(n-2)+O(n) ? Tabikide hayır. Zaman/Parçalanmış çözümler kısmını biz hatırlama yöntemini kullanarak O(1) olarak hesaplıyoruz parçalanmış çözümlerde n e eşit olduğundan T(n) = O(n) oluyor.

*Farklı kaynaklarda Memorize,Remember,memoize şeklinde geçebilir bu kavram.