Batu Incecay Rotating Header Image

best case

Algoritma Analizi

Algoritma, bir problemi çözmek için kesin ve açık bir şekilde belirtilmiş bir dizi talimat olarak tanımlanabilir. Bir algoritma etkin (effective), belirli (definite), doğru (correct) ve sonlu (finite) olmalıdır.

Örneğin n elemanlı bir A dizisindeki girdi değeri bulan ve bulunduğu konumu geri döndüren (değer bulunamıyorsa -1 döndüren) algoritma şu şekildedir:

AramaAlgorithm

Biz algoritmanın etkinliğini tam olarak hesaplamak istiyoruz. Bu noktada öncelikle o algoritmadaki temel işlemi bulmalıyız. Yukarıda verdiğimiz arama algoritmasındaki temel işleme bir bakalım. Bu algoritma için temel işlem karşılaştırma işlemi. ( if A[i] = girdi] ) Temel işlemi bulduktan sonra bizi sonuca götürecek konu bu temel işlemin ne kadar tekrarlandığı.

Birkaç örnek üzerinden gidelim. Aşağıda aynı 7 elemana sahip ancak elemanları farklı şekilde sıralanmış 3 dizi var. Bu diziler üzerinde 1 değerini arayalım.

1, 6, 8, 9, 5, 7, 3                     7, 5, 9, 8, 1, 6, 3                      9, 8, 7, 6, 5, 3, 1

Algoritmayı 3 dizi için de uyguladığımızda karşılaştırma sayıları sırasıyla 1, 5, 7 şeklinde olacaktır. Gördüğünüz üzere algoritmanın etkinliği girdiye göre değişiyor; ancak biz girdiden bağımsız çalışıyoruz. Elimizde sadece algoritma var ve bu algoritmanın etkinliğini girdiden bağımsız olarak hesaplamamız gerekiyor. Bu noktada ne yapacağız? Bir algoritmayı analiz ederken; aksine bir söylem yoksa en kötü durumu hesaplarız. Ben burada en iyi, ortalama ve en kötü durumu hesaplayıp nasıl hesaplandığını göstereceğim.

En iyi durum en kolayı… Arama algoritmasını düşündüğümüzde en iyi durum nedir? Tabii ki ilk terimin minimum olmasıdır. Bu durumda da temel işlem yani karşılaştırma işlemi sadece bir kez yapılır. Yani sonuç 1’dir.

En kötü durum için işler biraz daha karmaşıklaşıyor. En kötü durum bizim örneklerimizde de görüldüğü gibi for döngüsüne her girdiğinde temel işlemimiz olan karşılaştırma işleminin yapılıp, dizinin son eleman olması (aranan elemanın dizide bulunamaması durumu da olabilir). Bunu da toplam sembolü ile şu şekilde belirtebiliriz. Döngü n kere döneceğine göre:

toplam olup, temel işlemin yapılma sayısını verecektir. Son örnekte de gördüğümüz gibi bu algoritma için en kötü durum tüm dizinin sonuna gelinmesidir. Bu durumda en kötü durum dizinin boyutu kadar olacaktır.

Son olarak gelelim ortalama durumuna… Aranan elemanın dizide bulunma ihtimali p olsun. Bu durumda hesaplamayı şu şekilde yapabiliriz.

Aranan elemanın dizinin 1. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin 1. elemanı ise yapılan karşılaştırma sayısı          : 1
Aranan elemanın dizinin 2. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin 2. elemanı ise yapılan karşılaştırma sayısı          : 2
Aranan elemanın dizinin 3. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin 3. elemanı ise yapılan karşılaştırma sayısı          : 3


Aranan elemanın dizinin n. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin n. elemanı ise yapılan karşılaştırma sayısı          : n
Aranan elemanın dizide BULUNMAMA ihtimali                                   : 1 – p
Aranan eleman dizide BULUNMUYORSA yapılan karşılaştırma sayısı       : n

Basit bir aritmetik ortalama alırsak:

ortalama

Eğer aranan elemanın dizide mutlaka bulunacağını kabul edersek; yani p = 1 olursa;
Ortalama karşılaştırma işlem sayısı: (n+1)/2 olur. Yani yaklaşık olarak dizinin eleman sayısının yarısıdır.

Basit bir algoritmanın en iyi, ortalama ve en kötü temel işlem sayılarını hesaplamayı görmüş olduk. Sonraki yazılarımda da bilinen bazı algoritmaları (örneğin ikili arama algoritması) analiz etmeye çalışacağım.