Karmaşıklık Analizi

Kotlin ile Veri Yapıları ve Algoritmalar yazı dizimize tüm hızıyla devam ediyoruz. Önceki yazılarda bahsedildiği üzere gündelik hayatımızda herhangi bir problem birçok farklı yol izlenerek çözülebilir. Aynı şekilde bilgisayar biliminde de farklı algoritmalar ile bir probleme farklı çözümler sunulabilir. Ancak burada önemli olan uygun olan algoritmayı seçmektir. Bunun için algoritma analizini bilmek gerekiyor. Karmaşıklık analizi, soruna en uygun algoritma seçmemizi sağlayan bir kavram olarak karşımıza çıkmaktadır.

Bir problemi çözerken olası tüm algoritmaları ele almamız, analiz etmemiz ve uygun olanı seçmemiz gerekiyor. Analiz işlemi iki temel kriter baz alınarak yapılır. Bunlar;

  • Time Complexity
  • Space Complexity

Time Complexity (Zaman Karmaşıklığı)

Bir algoritmanın verilen bir girdi için çıktı üretirken harcadığı veya ihtiyaç duyduğu süredir. Bu süre ne kadar kısa olursa algoritmanın performansı o kadar iyi olur. Zaman karmaşıklığını bir algoritmanın performansı olarak düşünebiliriz.

Bir bilgisayarın donanımı ne kadar iyi olursa olsun, her zaman için en performanslı algoritmayı seçmek mantıklı bir yaklaşım olacaktır. Donanımda yapılan iyileştirmeler ile beraber algoritmaların da iyileştirilmesi sağlanarak daha performanslı sistemler oluşturulabilir.

Space Complexity (Alan Karmaşıklığı)

Bir algoritmanın verilen bir girdi için çıktı üretirken kullandığı veya ihtiyaç duyduğu bellek alanıdır. Daha iyi alan karmaşıklığına sahip olan bir algoritma bellekte daha az alan kullanır. Böyle bir algoritma sistem kaynaklarını daha az tüketir. Her ne kadar sistem belleğini arttırmak akla gelen bir çözüm olsa da, her zaman için daha az alan tüketen bir algoritma seçmek mantıklı bir yaklaşım olacaktır.

Bir algoritma aşağıdaki davranışları sergileyebilir;

  • Hızlı olup ve daha az bellek alanına ihtiyaç duyabilir.
  • Hızlı olup ve daha çok bellek alanına ihtiyaç duyabilir.
  • Yavaş olup ve daha az bellek alanına ihtiyaç duyabilir.
  • Yavaş olup ve daha çok bellek alanına ihtiyaç duyabilir.

Bu davranışlar içinde şüphesiz ilk davranışa sahip olan algoritmaları tercih etmek, son davranışa sahip olan algoritmalardan ise olabildiğince kaçınmak gerekiyor. Ancak elinizde bir problemin çözümüne ait iki algoritma varsa ve bu algoritmalar ikinci ve üçüncü davranışları sergiliyorsa bu durumda size uygun olan algoritmayı seçmeniz gerekiyor. Eğer hız önemli ise ikinci davranışı sergileyen algoritmayı, eğer daha az bellek alanı tüketmek önemli ise üçüncü davranışı sergileyen algoritmayı seçmeniz gerekir.

Bir algoritmanın analizini yaparken aşağıdaki sorulara cevap aranır:

  • Çıktının üretilmesi veya hesaplanması ne kadar zaman alır?
  • Sorunu çözmek için ne kadar hafıza gerekir?
  • Veri girişi arttığında nasıl davranır?
  • Daha hızlı ya da daha yavaşlıyor mu? Daha yavaşsa, ne kadar yavaş? Giriş boyutunun iki katı için dört kat yavaşlıyor mu?
  • Veri girişi büyüklüğü ile zamanın bir ilişkisi var mı?

Notation Nedir?

Bu başlık altında karmaşıklık analizini nasıl yapacağımız öğreneceğiz. Karmaşıklık analizi yapılan bir algoritmanın farklı gösterimler ile temsil edilmesi işlemine notation denir. Bir algoritma verilen giriş verilerinin büyüklüğüne bağlı olarak farklı şekillerde davranabilir. Örneğin; 1 MB veriyi işleyen bir algoritma hızlı sonuç verirken, 1 GB veri ile karşılaştığı zaman daha yavaş bir şekilde sonuç üretebilir. Bu sebeple, olası her durumun karmaşıklığını analiz etmemiz gerekiyor.

Bir algoritma analiz edildikten sonra üç şekilde gösterilebilir:

  • Worst case: Çıktının üretilmesi için bir algoritmanın ihtiyaç duyduğu maksimum süreyi tanımlar. Buna Big O notasyonu ( O ) da denir.
  • Average case: Farklı boyutlardaki girdiler için çıktı üretmekte bir algoritmanın ihtiyaç duyduğu ortalama süreyi tanımlar. Buna Teta notasyonu ( θ ) da denir.
  • Best case: Çıktının üretilmesi için bir algoritmanın gerektirdiği minimum süreyi tanımlar. Buna Omega notasyonu ( Ω ) da denir.

Bir algoritmayı analiz etmek için yapılacak ilk işlem algoritmanın kaç adımda bittiğini tespit etmektir.

fun main() {
    var name = readLine()!!
    for(i in name)
        println(i)
}

Yukarıda verilen programı ele alırsak;

  • var name = readLine()!!, satırı 1 kabul edilir.
  • for döngüsünde girilen verinin uzunluğu (N) kadar çalışacağı için burası N defa çalışır.

Bu durumda algoritma N+1 kadar sürede çalışır. Karmaşıklık analiz yapılırken alt dereceler yok sayılabilir. Bu durumda bu algoritmanın çalışma zamanı N olur.

Bu örnek uygulama oldukça basittir. Ancak kodumuz karmaşık bir hal alınca hem komutları saymak hemde analizi yapmak oldukça zor olmaktadır. Bundan dolayı analiz işlemi yapılırken şunlara dikkat etmekte yarar var:

  • Sabit olan değerler görmezden gelinebilir. Yukarıdaki örnek algoritma için bulunan N+1 çalışma zamanında, sabit olan 1 değerini yok sayabiliriz. Yani giriş baz alındığı zaman sadece değişen faktörleri göz önüne alırız. Burada N değişken olduğu için sadece bu değeri çalışma zamanı olarak kabul ettik.
  • Bu bilgilere göre aşağıdaki çıkarımlarda bulanabiliriz.
    • f(n) = 10 ise f(n) = 1 kabul edilir.
    • f(n) = 7 + 10n ise f(n) = n kabul edilir.
    • f(n) = n2 + 10n + 7 ise f(n) =n2 kabul edilir.
  • Ayrıca şunları bilmekte de yarar var:
    • Herhangi bir algoritmada döngü yok ise f(n) = 1 olur.
    • Bir algoritmada döngü var ise f(n) = n olur.
    • Bir algoritmada içiçe döngüler var ise f(n) = n2 olur.

Bu bilgilerden sonra örnek bir algoritmanın karmaşıklık analizini yapalım.

var arr = arrayListOf<Int>(5,9,12,2,89,100,1)
var item= readLine()!!.toInt()
for (i in arr.indices) {
    if (arr[i] == item) {
        print("Sayı bulundu.")
    }
}

Yukarıda klavyeden girilen bir sayının dizide aranması sağlanmıştır. Şimdi, bu algoritmanın en kötü, en iyi ve ortalama durumunu analiz etmeye çalışalım.

  • 5 sayısı aranırsa, döngü bir kez çalışır ki biz buna best case yani en iyi durum diyoruz.
  • 2 sayısı dizinin tam ortasında yer aldığı için döngünün n/2 kez çalışması gerekir ki biz buna average case yani ortalama durum diyoruz. n dizinin uzunluğudur.
  • 1 sayısı dizinin sonunda olduğu için döngünün n kez çalışması gerekir ki biz buna worst case yani en kötü durum diyoruz. Eğer aranan eleman dizide bulunmuyorsa yine en kötü durum gerçekleşir ve döngü n kez çalışır.

Bu algoritma için analizlerimiz şöyledir:

  • Best Case – Ω(1)
  • Average case – θ(n/2)
  • Worst case – O(n)

Görüleceği üzere aranan elemanın dizideki konumuna bağlı olarak döngünün çalışması değişkenlik göstermektedir. Analiz sırasında tüm durumların ele alınması ve özellikle en kötü durum için en iyi analiz işleminin yapılması gerekmektedir. Çünkü en kötü durum istenmeyen durum olup bunun önüne geçilmesi gerekiyor. Yazı dizimize daha sonra kaldığımız yerden devam edeceğiz. Şimdilik hoşça kalın.

**Bana en büyük desteğiniz yazılarıma yorum yapmanız ve paylaşmanızdır.