Algoritmalar Ve Programlama Dersi 5. Ünite Özet

Fonksiyonların Büyümesi

Tasarladığımız algoritmaları analiz ederken, az sayıda girdi için sonucun ne kadar hızlı hesapladığını incelemek çok anlamlı değildir. Örneğin, yalnızca 10 tane sayıyı sıralayacak sıralama algoritmalarını düşünelim. Böyle bir işlem için gerek kabarcık sıralaması gerek birleştirme sıralaması algoritması çok kısa bir sürede sonuç verecektir. Başka bir ifadeyle, girdi sayısı az olduğunda iki algoritma arasındaki farkı net bir şekilde göremeyiz. Ancak, 10 tane yerine 1 milyon tane sayıyı sıralamak istediğimizi düşünürsek, böyle bir durumda girdi miktarı oldukça büyük olduğu için iki algoritmanın zaman karmaşıklığı arasındaki fark kolayca anlaşılacaktır. Böylelikle, zaman karmaşıklığı daha düşük olan birleştirme sıralama algoritması çok daha çabuk sonuca ulaşacaktır. İkinci bir örnek verecek olursak, 1000. Fibonacci sayısını hesaplamak, beşinci Fibonacci sayısını hesaplamaktan daha uzun zaman alacaktır. Bir algoritmanın zaman karmaşıklığı, girdi sayısının yeterince büyük olduğu varsayılarak hesaplanmaktadır. Kabarcık sıralaması n2 zaman alırken, birleştirme sıralaması n logon zaman almaktadır. Bu durumda, 1 milyon tane sayıyı sıralamak istediğimizde, kabarcık sıralaması 1012 birim zaman alacakken, birleştirme sıralaması 2x107 birim zaman alacaktır. Çalışma zamanındaki farklılık, bu verilerden anlaşılabilir. Üstel ya da faktöriyel karmaşıklığa sahip algoritmalar çok yavaş çalışacaktır. Bu nedenle, üstel karmaşıklığa sahip algoritmalar yalnızca az girdi sayısına sahip problemler için kullanışlıdır.

Algoritmaların En Kötü Durum, En iyi Durum ve Ortalama Durum Verimlilikleri

Algoritmaların durum verimlilikleri verilen girdiye göre değişebilmektedir. Örneğin, bir lineer sıralama algoritmasını ele alalım. Bu algoritma, verilen bir sayının dizideki elemanlardan biri olup olmadığının sonucunu döndürmektedir. Bu algoritmada verilen sayı, dizideki ilk elemandan başlayarak sırasıyla dizinin tüm elemanlarıyla karşılaştırılmaktadır. Bulmak istediğimiz değerin dizideki ilk elemana eşit olması, arama probleminde karşılaşabileceğimiz en iyi durumdur. Böyle bir durumda, dizinin ilk elemanı ile karşılaştırmayla hemen sonuca ulaşıp dizinin diğer elemanlarıyla karşılaştırmaya gerek kalmayacaktır. Bu durum, lineer arama algoritmasının en uygun girdi için verimliğidir. Lineer arama örneğinden de anlaşılacağı üzere bir algoritmanın en iyi durum verimliliği, en uygun girdi durumundaki algoritma karmaşıklığıdır. Ancak en iyi durum verimliliği çok fazla anlam ifade etmemektedir. Çünkü çoğu zaman verilen girdiler sürekli değişmektedir ve en uygun girdinin denk gelme olasılığı oldukça düşüktür. Karşılaşabileceğimiz olası bir başka durum ise girdi verisinin algoritma için en kötü olduğu durumdur. Lineer arama algoritmasını düşünecek olursak aradığımız elemanın dizinin son elemanı olması veya dizide hiç bulunmaması karşılaşabileceğimiz en kötü girdi durumlarıdır. Bu durumlarda, lineer arama algoritması ilk elemandan son elemana kadar sırasıyla bütün elemanlar için arama işlemini gerçekleştirecektir. Başka bir ifadeyle, en kötü durum verimliliği söz konusudur. Algoritmaların karmaşıklığını hesaplarken genellikle en kötü durumu göz önüne almaktayız. Son olarak bakacağımız durum ise ortalama durum verimliliğidir. Burada ise algoritmamızı farklı girdiler için pek çok kez çalıştırarak çalıma sürelerinin ortalamasını alırız. Böylece, ortalama durum verimliliğini elde etmiş oluruz. Lineer arama algoritmasını düşünecek olursak verilen girdiye göre 1. 2. 3. … N. gibi adımlarda aradığımız sayıyı bulabiliriz. Bu olasılıkların hepsinin ortalamasını aldığımızda (N/2)’neci adımda, yani dizinin orta elemanında sonucu bulmamız gerekmektedir. Bu değer ise lineer arama algoritmasının ortalama durum verimliliğidir.

Asimptotik Gösterimler

Bir algoritma çalıştığında kaç birim adımda sonuca ulaşacağı hesaplanarak aynı problemi çözen farklı algoritmaların verimliliği karşılaştırılabilir. Bilgisayar bilimcileri, fonksiyonların büyümesini de göz önünde bulundurarak algoritmaları karşılaştırırken kullanılmak üzere üç tane gösterim tanımlamıştır:

• Büyük O Gösterimi
• Büyük Ω Gösterimi
• Büyük Θ Gösterimi

Büyük O Gösterimi Matematiksel gösterimin dışında tanımlayacak olursak büyük O gösterimini kullandığımızda analiz ettiğimiz algoritmanın çalışma zamanının belirli bir girdi değerinden sonra bu gösterimdeki fonksiyondan daha küçük olarak çalıştığını garanti etmektedir. Başka bir ifadeyle, algoritmamız O(n2 ) mertebesinde ise algoritmamız içerisindeki işlemlerin n2 adımına eşit ya da daha az adım gerektirdiğini göstermektedir. Büyük O gösterimiyle bir fonksiyonun üst sınırını belirtmiş oluruz.

Büyük Ω Gösterimi Algoritma analizinde kullanılan ikinci gösterim, büyük Ω gösterimidir. Bu gösterim ile verilen bir algoritmanın değerinin, Ω gösterimindeki fonksiyonun değerinden daha büyük olduğunu göstermektedir. Yani Ω gösterimi fonksiyonun alt sınırını belirtmektedir.

Büyük Θ Gösterimi Büyük Θ gösteriminde, algoritmanın fonksiyonunu alttan ve üstten sınırlayacak bir fonksiyon bulmak istenir.

Sabit sınıfı genellikle en iyi durum verimliliklerinde karşımıza çıkabilmektedir. Logaritmik sınıf algoritmalarında ise problemin büyüklüğü her bir iterasyonda belirli bir sayıya (genellikle 2) bölünmektedir. Lineer sınıfındaki algoritma, dizide verilen bütün elemanların üzerinden tek tek gitmektedir. Yarı doğrusal sınıfındaki algoritmalar çoğunlukla böl-birleştir algoritmalarıdır. İkinci derece (kareli) sınıfındaki algoritmalarda iki tane iç içe döngü bulunmaktadır.

Üçüncü derece (kübik) sınıfındaki algoritmalarda üç tane iç içe döngü bulunmaktadır. Üstel sınıfındaki algoritmalar, bir kümenin bütün alt kümeleri üzerinde işlem yapmaktadırlar. Faktöriyel algoritmalarında bir kümenin bütün Per mutasyonları üzerinde işlem yapılmaktadır.

Özyinelemeli Olmayan Algoritmaların Analizi

Bir algoritmayı analiz etmek, genel olarak aşağıda verilen adımlardan oluşmaktadır (Devitin, 2012).

1. Problemin girdi büyüklüğünü veren parametre belirlenir.
2. Algoritmanın temel operasyonu belirlenir.
3. Temel operasyonun sadece girdi büyüklüğüne bağlı olarak mı değiştiği kontrol edilir. Eğer başka parametrelere göre de değişiyorsa bunlar belirlenir.
4. Temel operasyon için toplam ifadesi bulunur.
5. Toplam ifadeleri için verilen standart formüller ve kurallar kullanılarak algoritmanın ait olduğu verimlilik sınıfı bulunur.

Algoritma Analizi ile İlgili Genel Kurallar

Algoritmaların analizini yaparken aşağıda verilen dört durumun analizinden faydalanabiliriz.

For Döngüsü: for döngüsünün çalışma zamanı, içerisindeki operasyonların çalışma zamanının iterasyon sayısı ile çarpımı kadardır.

İç içe for döngüsü: Öncelikli olarak içteki döngünün analizi yapılır. Daha sonra dıştaki döngünün analizi yapılır. İç içe döngünün çalışma zamanı iki döngünün çalışma sayılarının çarpımına eşittir.

İki tane arka arkaya fora döngüsü: Arka arkaya iki tane döngü söz konusu olduğunda, iki döngünün de çalışma sayıları bulunur ve bu sayılar birbiriyle toplanır.

if/else deyimi: if ya da else kısmındaki çalışma zamanından hangisi daha büyükse o dikkate alınır.

Algoritma Analiz Örnekleri

İlk örneğimiz, bir önceki bölümde tasarladığımız bir dizinin en büyüğünü (maksimum) bulma algoritmasıdır. Bu algoritmanın girdileri, dizinin kendisi ve dizideki eleman sayısıdır. Algoritmanın temel operasyonu for döngüsünün yer aldığı kısımdır. Bu kısmı analiz ettiğimizde, algoritmanın karmaşıklığını belirlemiş oluruz.

Özyinelemeli Algoritmaların Analizi Özyinelemeli fonksiyonların analizini yaparken gerçekleştirilecek işlemler aşağıdaki gibidir (Devitin, 2012):

1. Girdi büyüklüğünü veren parametre belirlenir.
2. Algoritmanın temel operasyonu belirlenir.
3. Girdi parametresine göre problemin temel operasyonunun çalışma sayısının değişip değişmeyeceği belirlenir.
4. Başlangıç koşulları ile birlikte algoritmanın özyinelemeli fonksiyon bağıntısı yazılır.
5. Fonksiyonların büyümesi ve toplam ifadeleri kullanılarak özyineleme bağıntısı çözülür ve zaman karmaşıklığı bulunur.

Özyinelemeli algoritmalar için verilebilecek diğer bir örnek, ikili arama algoritmasıdır. Bu algoritmada elimizde küçükten büyüğe doğru sıralı bir dizi bulunmaktadır. Bu sıralı dizide, belirli bir elemanın olup olmadığı araştırılmaktadır İkili arama algoritmasında dizi sıralı olduğu için arama işlemini daha hızlı yapabiliriz. Bu arama algoritmasında öncelikle dizinin ortasındaki elemanı bulup aradığımız elemanı bu eleman ile karşılaştırmaktayız. Aradığımız eleman ortadaki elemana eşit ise ortadaki elemanı cevap olarak döndürülür. Aradığımız eleman ortadaki elemandan küçük ise dizi sıralı olduğundan elemanımızı dizinin sol tarafında özyinelemeli olarak aramaya devam ederiz. Benzer şekilde, aradığımız eleman ortadaki elemandan büyük ise dizinin sağ tarafında, yani daha büyük olan kısımda aramaya devam ederiz. Bu ikiye bölme işlemi, aranan eleman bulununcaya kadar devam eder.