Algoritmalarda Zaman ve Uzay Karmaşıklığı
İnsanların hayatlarının verdikleri kararlar ve sonrasında bu kararlar özelinde katlandıkları sonuçlardan ibaret olduğunu düşünürüm hep.
İşin teknik taraflarına girmeden önce basit bir soruyla konuya sizleri hazırlamak istiyorum. Bir kış günü arkadaşlarımız ile buluşmak üzere dışarı çıkacağımızı düşünelim. Nasıl giyinirdiniz? Kıyafetlerimiz arasından mevcut duruma en uygun kombin hangisi ise onu seçerdiniz değil mi? Dolabımızda ne kadar çok kıyafetimiz var ise süre ve diğer değişkenler de bu ölçüde değişiklik gösterecektir.
Şimdi gelelim bizim konumuza tahminimce hepimizin katılacağı gibi projelerimizi geliştirirken karşılaştığımız bir sorunun n tane çözümü olduğunu az çok hepimiz kabul ederiz. Peki söz konusu bir adet problemimiz ve elimizde de iki tane çözüm algoritmamız olsun. Bu karmaşa içerisinde bizim ihtiyacımız olan yada en mantıklı tercihin hangisi olduğuna nasıl karar verebiliriz.
İşte bu noktada cevabı çok ta uzaklarda aramamıza gerek yok. Bir önceki cümlemize döndüğümüz zaman kullandığımız bir kelime dikkatinizi çekmiştir mutlaka. KARMAŞA.
Burada söz konusu olan karmaşa aslında algoritmamızın veririmliliğini etkileyen en önemli faktörlerdir.
Verimliliğin iki temel karmaşıklık ölçüsü vardır. Bunlar Zaman ve Uzay Karmaşıklığıdır (Time & Space Complexity).
Gelelim bu Zaman ve Uzay Karmaşıklığı kavramlarının teoride ne anlam ifade ettiklerine.
Zaman Karmaşıklığı; Bir algoritmanın yaşam döngüsü boyunca ihtiyaç duyduğu toplam süreyi ifade eder.
Daha önce bahsettiğimiz n değerimiz ne kadar farklılık gösterirse sonucumuzun da bu ölçüde n değerimiz ile ilişkili olduğunu görürüz ve bir algoritmanın performansı bahsi geçen konulardan dolayı değişiklik göstereceğinden en kötü durum zaman karmaşıklığını kullanırız. Çünkü ilgili sonuç herhangi bir girdi boyutu için maksimum süreyi ifade eder.
Şimdi de Zaman Karmaşıklığını basit bir örnek ile açıklamaya çalışalım.
Örnek : 100 kişilik bir sınıf hayal edelim. Bu 100 kişi içerisinden bir arkadaşımıza bir önceki derste bir kalem verdiğimizi düşünelim. Şimdi o kalemi geri istiyoruz. Bu kalemi bulmanın bazı yollarından bahsedelim.
- Yöntem — O(n kare): Gidip sınıftan denk geldiğimiz ilk öğrenciye kalemin onda olup olmadığını sorarız. Sonucun olumsuz olması durumunda aynı kişiye tek tek diğer arkadaşlarında olup olmadığını sonucu görene kadar sormaya devam ederiz.
- Yöntem — O(n) : Her öğrenciye gidip tek tek kalemin kendisinde olup olmadığını sorarız.
- Yöntem — O(log n) : Söz konusu sınıfı iki ayrı gruba ayırırız(A ve B). Kalem A grubunda mı B grubunda mı? Sonra sonucu doğru olan grubu alıp tekrar ikiye bölüyoruz ve tekrar hangi grupta olduğunu soruyoruz ve bu şekilde sonuca ulaşıncaya kadar devam ediyoruz.
Kalemin hangi öğrencide olduğunu sadece bir öğrenci biliyorsa söz konusu durum için O(n kare) aramasını yapmamız gerekir. Kalem bir öğrencide olsaydı ve kalemin onda olduğunu sadece o öğrenci biliyor olsaydı. Bu durumda da O(n) aramasını yapmamız gerekir. Kalemin kimde olduğunu tüm öğrencilerin bildiği durumdaysa O(log n) aramasını yaparız.
Bu noktada şu cümleyi tekrar etmekte fayda var. Programın yürütülmesi sırasında alınan girdilere göre zamanın büyüme oranıyla ilgilendiğimizi unutmayalım.
Uzay Karmaşıklığı; Biz işlemlerimizi gerçekleştirirken daima bir bellek alanına ihtiyaç duyarız. Algoritmamız sonlanıncaya kadar girdi değerleri de dahil olmak üzere kullanılan bellek miktarını ifade eder.
Yukarıdaki kod bloğumuzdaki number1, number2, number3 ve result tam sayı türünde değerler olduğu için her biri dört byte yer kaplar. Böylece toplam bellek gereksinimi (4(4) + 4) = 20 byte bellek kullanılmış olur. Sonradan eklediğimiz dört değeri dönüş değerini ifade eder.
Burada bellek gereksinimimiz sabit olduğundan Sabit Uzay Karmaşıklığı (Constant Space Complexity) olarak tanımlanır. Tam tersi bir durum da ise Doğrusal Uzay Karmaşıklığı (Linear Space Complexity) ismini alır.
İki temel kavramımızı da barındıran son bir örnek ile yazımızı sonlandıralım.
Herhangi bir sayının (n) karesini bulmaya çalışalım. Hemen aklımıza gelen iki yönteme beraberce bakalım.
- Yöntem : n sayısıyla başlayarak ona n ekleyerek birkaç kez döngü çalıştırmak olabilir.
2. Yöntem : n sayısını yine kendisiyle çarparak sonuca ulaşmak.
Burası için de yinelemek gerekirse programın yürütülmesi sırasında alınan girdilere göre zaman ve değişkenlerimizin kapladığı alanlar özelinde düşündüğümüzü unutmayın.
Umarım faydalı olmuşumdur. Bir başka konuda görüşmek üzere…
Kaynaklar:
