1.0 Algoritma Analizi ve Complexity Nedir?

1.1 Algoritma Analizi:

Algoritma analizi bilgisayar biliminde bir algoritmayı çalıştırabilmek için gereken kaynakların miktarının tespitidir.

Biz kodumuzda hafıza ve zamanı olabildiğince verimli kullanmak isteriz. Bir algoritma yazarken hem hafıza hem zamandan tasarruf edebilecek yazabiliyorsak o algoritma çok iyi bir algoritmadır ancak genellikle ikisinden birlikte tasarruf edemediğimiz için duruma göre birinden fedakarlık veririz. Algoritma analiziyle de bunları analiz ederiz. Peki bunları nasıl analiz edeceğiz? Burada complexity (karmaşıklık) kavramı devreye girer. Complexity bir problem veya algoritmanın çözüme ulaşmadaki karmaşıklığını ölçmek için kullanılır.

1.2 Complexity Theory(karmaşıklık teorisi):

Karmaşıklık teorisi, sistemin parçaları arasındaki etkileşim sonuçlarına bağlı olarak karmaşık sistemlerdeki ilişkilerin doğrusal olmayan ve tahmin edilemeyen bir nitelik taşıdığını ifade etmektedir. Buradan algoritmaların sonuçlarını kesin olarak tahmin edemeyeceğimizi bu yüzden en iyi durum ile en kötü durumlara göre bir çıkarım yaptığımızı düşünebiliriz.

1.3 Complexity Classes (karmaşıklık sınıfları):

1. small-o(küçük-o)

2. big-o(büyük-o)

3. Theta

4. Big-omega

5. Small-omega

• Bilgisayar bilimlerinde bu 6 adet karmaşıklık sınıfı kullanılır.

• Bu karmaşıklık sınıfları aynı fonksiyonun farklı özelliklerini anlatan sınıflardır.

• Bu sınıflar sayesinde algoritma hakkında bilgi alabiliyoruz. Bu bilgiler ne kadar zaman ve hafızaya ihtiyaç duyduğumuzun bilgileridir.

Bu sınıfları somutlaştırmak için şöyle bir örnek verilebilir. Bunları 5 farklı büyüme hızına sahip bitkiler gibi düşünebiliriz. Biz bu bitkilerin büyüme hızlarını karşılaştırmak istiyoruz. Bunun içinde asimtotik notasyonları anlamaya çalışıyoruz. Peki asimtotik notasyonlar nedir ? Asimtotik notasyon bir algoritmanın veri büyüklüğüne bağlı olarak nasıl davrandığını gösteren matematiksel bir ifadedir. Bir algoritmanın hızını veya verimliliğini ölçerken kullandığımız bir sistemdir. Asimptotik notasyonları şimdilik bir kenara bırakıp complexity classlarımıza geri dönelim. 5 tane karmaşıklık sınıfı olduğundan bahsetmiştik. Peki bunlar ne işe yarıyor?

1.3.1 Small-o

Bir fonksiyon belirlerken belirtilen sınırlardan kesinlikle küçük kaldığını belirtmek için kullanılır.

Örnek: Bir çiçeğimiz var ve onun asla 10 metre olamayacağını biliyoruz. O zaman bu çiçeğe o(10m) diyebiliriz.

1.3.2 Big-o

Bir fonksiyonun worst-case yani en kötü durumudur.

Örnek: Bir çınar ağacı en fazla 30 metre olabilir dersek bu Big-o olur. Çınar ağacı 30 metreyi bulur mu bilemeyiz ama en fazla o kadar olabilir.

1.3.3 Theta

Bir fonksiyonun tam olarak hangi aralıkta büyüyeceğini kesin olarak biliyorsak kullanırız.

Örnek: Bir ağaç en az 10 metre en fazla 18 metre olabileceğini biliyoruz. O zaman Θ(14m) diyebiliriz. Yani fonksiyonun büyüme değerinin ortalama değeridir.( Average-case)

1.3.4 Big omega

Bir fonksiyonun minimum ne kadar büyüyebileceğini söylemek için kullanılır.

Örnek: Bir palimiye ağacının en az 5 metre olacağını biliyorsak bunu söylemek için kullanabiliriz. O zaman Ω(5m) diyebiliriz. Yani bir fonksiyonun en az büyüme hızını ifade etmede kullanırız ve bu da en iyi durum olur bizim için.(Best-case)

1.3.5 Small omega

Bir algoritmanın kesin olarak bir diğerinden hızlı büyüdüğünü gösterir.

Örnek: Diyelim ki iki farklı bitki var:

Bambu her yıl iki katına çıksın

kaktüs her yıl 1 cm uzasın

bambu her zaman kaktüsten hızlı büyür

Örnek2: iki algoritmamız olsun

algoritma A: n’2 adımda çalışıyor olsun

algoritma B: n adımda çalışıyor olsun

algoritma A her zaman algoritma Bden çok daha hızlı büyür.

Bunu n’2 = w(n) şekinde gösteririz.