Dinamik programlama, problem çözüm yöntemlerinden biridir. Amaç, sıralı benzer işlemleri tekrarlayarak oluşan performans ve zaman kaybını en aza indirmektir.

Bir kodun kısa olması, programın daha performanslı çalışacağı anlamına gelmez. Daha çok alt parçadan oluşan ve daha uzun bir kod bloğuna sahip bir çözüm diğerine göre daha performanslı çalışabilir. Konunun örneği olarak geçen sene hazırladığım programı, dinamik programlama ile fibonacci serisi hesabı ödevini paylaşacağım.

Programı kısaca açıklamak gerekirse; girilen bir sayının fibonacci değerini, iki fonksiyona gönderiyorum. Bu fonksiyonlardan ilki problemi dinamik programlama yöntemi ile çözerken, diğeri recursive kavramı ile çözüyor. Aradaki performans farkı şu noktada oluşuyor:

Dinamik Fibonacci fonksiyonunda hesaplanan her değer bir diziye atılıyor. Yani yeni bir değer hesaplanırken sıfırdan bir hesaplama durumu söz konusu değil. Önceki değerler zaten dizide tutuluyordu.

REcursive Fibonacci fonksiyonunda ise her yeni değer için tüm hesaplamalar sıfırdan yapılıyor. Yani zaten daha önce hesaplanan değerler defalarca yeniden hesaplanıyor. Bu da haliyle büyük bir performans kaybına neden oluyor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using System;

namespace dinamikFibonacci
{
    class Program
    {
        static int counterDinamik = 0;
        static int counterRecursive = 0;
        public static void Main()
        {
            int sayi;            
            Program prg = new Program();
            sayi = Convert.ToInt16(Console.ReadLine());
            Console.WriteLine(dinamikFibonacci(sayi));
            Console.WriteLine(fibonacciRecursive(sayi));
            Console.WriteLine("Dinamik fibonacci fonksiyonunun çalışma sayısı: " + counterDinamik + "\nRecursive fibonacci fonksiyonunun çalışma sayısı: " + counterRecursive);
        }
        public static int dinamikFibonacci(int sayi)
        {
            counterDinamik++;
            int[] sayilar = new int[sayi + 2];
            for (int i = 0; i <= sayi; i++)
                if (i == 0 || i == 1)
                {
                    sayilar[0] = 0;
                    sayilar[1] = 1;
                }
                else
                {
                    sayilar[i] = sayilar[i - 1] + sayilar[i - 2];
                }
            return sayilar[sayi];
        }
        public static int fibonacciRecursive(int sayi)
        {
            counterRecursive++;
            if (sayi == 0)
                return 0;
            if (sayi <= 2)
                return 1;            
            return fibonacciRecursive(sayi - 1) + fibonacciRecursive(sayi - 2);
        }
    }
}

Post comment

Time limit is exhausted. Please reload the CAPTCHA.