Dergimizin bu yılki ilk sayısıyla bütün bilgisayar dünyasına merhaba derken, bu ay algoritmalarda karmaşıklık (complexity) konusuna göz atacağız. Hepimizin bildiği gibi; "algoritma" kelimesi, bir problemi çözmek için izlenen sistematik işlemler kümesi anlamındadır. Algoritmalar hakkında ayrıntılı bilgi için e-bergi'nin Şubat 2008 sayısındaki ”Algoritma” yazısına ve çeşitli algoritma türleri için “Sıralama Algoritmaları” ve “Arama Algoritmaları” adlı yazılara başvurabilirsiniz. Bu yazıda algoritma türlerinden çok, bir algoritmanın kalitesinden, yani verimliliğinden bahsedeceğim.

Bir sorunu çözmek için belirli bir algoritmayı izledik diyelim, peki bu algoritma bizi ne kadar uğraştırdı? Daha verimli bir şekilde sorunumuzu halledebilir miydik? Bu soruları cevaplayabilmek için ilk önce "verimlilik" (efficiency) kavramının biraz oturması gerek. Günlük hayattan örnek vermek gerekirse, apartman kapısından eve ulaşabilmek için iki seçeneğimiz var diyelim; asansör ve merdiven. İkisi de bizi aynı amaca sorunsuz bir şekilde ulaştırıyor; fakat neden bazılarımız merdiven çıkarken bazılarımız asansörü tercih ediyor? İlk önce katettiğimiz yola bakalım, merdivende döne döne yolumuz uzarken, asansörde neredeyse düz bir çizgi halinde eve ulaşıyoruz. Peki zaman açısından ele alalım, üçüncü kata çıkmak isterken asansörün on beşinci kattan gelmesini bekliyoruz, hımm merdiven çok daha hızlı bir algoritma sanırım. Peki asansör zemindeyse ve beklemiyorsak? Dış etkenlere göre algoritmamızı değiştiriyoruz demek.. Bir de sağlık açısından bakalım iki algoritmamıza, merdiven çok daha sağlıklıyken asansör biraz daha gölgede kalıyor.

Bütün bunları basit olarak düşünmenin yanı sıra, diyelim ki bu algoritmaları bir kağıda yazıp, asansör ve merdiven kullanım kılavuzları yazacağız (evet çok uç bir örnek oldu; ama bir algoritmayı kodlamak, yani karşımızdaki pek akıllı olmayan makinaya derdimizi anlatmak da sadece bundan ibaret :) ).

Merdiven algoritması:

  1. basamakları çık
  2. kat numarasına bak
  3. evinin olduğu katsa dur
  4. değilse (1)e dön
  5. evin kapısını aç

Asansör algoritması:

  1. asansörün yukarı düğmesine bak
  2. asansörü bekle
  3. asansörün gelme ışığı sönerse (1)e dön
  4. asansör geldiyse kapısını aç
  5. içeri gir
  6. evinin katına bas
  7. asansör durana kadar bekle
  8. asansör durduğunda kat numarasına bak
  9. kendi katınsa asansörden in
  10. değilse (7)ye dön
  11. evin kapısını aç

Farkındaysanız uygulama açısından yoldan tasarruf etmemizi sağlayan asansör algoritması, adım adım anlatmaya veya kodlamaya geçince ne kadar da uzun sürdü. İşte berimsel algoritmalar için de, birçok türden ele alınarak verimlilikleri açısından karşılaştırılmaya ihtiyaç duyulmuşlardır. Bu yüzden karmaşıklık kavramı (complexity) ortaya sürülmüştür. Kısaca karmaşıklık, iki algoritmanın karşılaştırılabilmelerini sağlayan mekanizmadır. Ancak karmaşıklık ve performans arasındaki ince ayrımın yapılması gerek: Performans bir program çalıştırıldığında kullandığı zaman ve bellek miktarıyken; karmaşıklık aynı programın veya algoritmanın girdilerinin değişimiyle orantılı olarak kaynak gereksiniminin değişme oranıdır. Performans, karmaşıklığa, kodun çalıştırıldığı makinaya, derlendiği derleyiciye göre değişirken; karmaşıklık bunlardan etkilenmez.

Berimsel Karmaşıklık Teorisi (Computational Complexity Theory)

Algoritmaların verimliliğini biraz olsun örneklendirebildiğimi düşünerek, artık işin bilimsel tarafına geçebiliriz. Computational Complexity Theory, bilgisayar biliminde önemli yer tutan hesaplama teorisinin (theory of computation) bir dalıdır. Algoritmaların çalışması için ihtiyacı olan kaynaklarla ilgili sorunları ve bunların minimuma düşürülüp daha verimli algoritmalar elde edebilmeyi inceler. Teorinin en belirgin sorusu şudur; "Bir algoritmanın aldığı girdi miktarı arttıkça, kullandığı zaman ve bellek gereksinimleri nasıl değişir? Bu değişimin etkileri nelerdir?". Bu verileri, algoritmaları veya berimsel problemleri ölçebilmek için kullanır. Karmaşıklığa belitsel yaklaşımı geliştiren Manuel Blum, berimsel karmaşıklığın kategorilere ayrılmadan en genel şekilde incelenmesinde olanak sağlamıştır. Zaman karmaşıklığı (time complexity) ve alan karmaşıklığı (space complexity) ise bu belitsel karmaşıklık ölçümünün sadece birkaç özel durumudur.

Zaman karmaşıklığı; genel bir problemin bir örneğini, en verimli algoritma ile çözmek için izlenen adımların, girdi miktarı cinsinden bir fonksiyon ile ifade edilmesidir. Mesela n uzunluğuda bir girdi verildiğinde log(n) adımda çözümlenen bir problem, log(n) zaman karmaşıklığına sahiptir. Tabi ki kaç adımda hesaplanacağı, algoritmanın çalıştırıldığı makineye veya kodlandığı dile de bağlıdır; ama bunlardan bağımsız olması için birazdan bahsedeceğim "Büyük O Gösterimi" (Big O Notation) gibi genellemeye yarayan gösterimler vardır. Alan karmaşıklığı ise, bir algoritmanın kullandığı alan veya bellek miktarıyla ilgilidir. O da Büyük O gösterimi ile ölçülür. Alan ve zaman karmaşıklığı dışında,dağınık sistemler için kullanılan iletişim karmaşıklığı ve boole devrelerinin karşılaştırılmasını sağlayan devre karmaşıklığı gibi karmaşıklık çeşitleri de vardır.

Bu teorinin en önemli yanlarından biri de, berimsel sorunları ve algoritmaları karmaşıklık sınıfları (complexity classes) denen kategorilere ayırmaya çalışmasıdır. Karmaşıklı sınıflarını başka bir yazımıza bırakarak, algoritmaların karmaşıklığının ölçülmesi için kullanılan yöntemlere bir bakalım.

Algoritmaların Analizi

Dediğim gibi algoritmaların kalitesinin ölçülmesi bilgisayar biliminde önemli bir konu. Ancak öncelikle şunu belirtmeliyim ki, bir algoritmanın verimliliği, çözülmesinde kullandığı sorunu ne kadar doğru çözdüğüne kesinlikle bağlı değil. Karşılaştırılan veya kalitesi ölçülen algoritmaların hepsinin kesin sonuca doğru bir şekilde ulaştığı var sayılır, nitekim bir algoritmanın en önemli özelliği her zaman doğru sonucu vermesidir. Ancak algoritmamızı veya programımızı düzgün bir şekilde ortaya koyduktan sonra bunun verimliliğinin ölçümüne geçebiliriz. Bu ölçümün çevreden ve platformdan bağımsız olup, sadece algoritma ve kullandığı kaynaklara özgü olması için bazı gösterimler kullanılır. Farklı algoritmalar, aynı görevi, farklı adımlarla daha az veya çok zamanda, daha az veya çok bellek kullanarak yerine getirebilir. Algoritmaların analizi bu açıdan, matematiksel altyapıya da dayanarak, sahte kodların teorik analizi ile en verimlisini bulmak için algoritmaları yarıştırır :) Ama bu yarışta güvendiğimiz araç "zaman" gibi soyut kavramlar değil de, daha genel olan asimptotik gösterimlerdir. Dilerseniz bunları incelemeye en çok kullanılan Büyük O Gösterimi ile başlayalım.

Büyük O Gösterimi (Big O Notation)

Bu gösterimdeki "O" basit bir fonksiyonun, daha karışık fonksiyonların büyüklükleri için asimptotik bir üst sınır ifade ettiğini gösterir. Bu limit fonksiyonu belirlemek için; girdi miktarı olan x'in, herhangi bir k sayısından büyükken, sonsuza gittiği varsayılır. f(x), yani algoritmamızın girdizaman veya girdialan fonksiyonu, x sonsuza giderken her zaman bir C*g(x) fonksiyonunun değerinden küçük değerler alır. Burada C herhangi bir katsayıdır, g(x) ise olası asimptotik fonksiyonumuzdur. Kısaca x>k sonsuza giderken, her zaman f(x) < C*g(x) eşitsizliğini sağlayan bir g(x) fonksiyonu varsa, f(x) fonksiyonunun karmaşıklığı O(g(x)) olarak gösterilir. “f(x)'i derecesi g(x)'tir” veya "f(x) g(x)'inci derecedir" denir.

f( n ) Є O( g(n) )

Böylece belli bir algoritmanın, durana kadar hangi sıklıkla işlem yapacağını söylemesiyle, oalgoritmanın verimliliğine Büyük O gösterimi sayesinde karar verebiliriz. Gelelim hesaplamaya. Programlarımızın hangi dilde kodlandığı, hangi bilgisayarda çalıştırıldığı veya hangi girdilerin kullanıldığı gibi dış değişkenlerden bağımsız olarak verimliliği ölçebilmemiz için; öncelikle programların karmaşıklıklarını Büyük O gösterimi ile yazmalıyız. Bunu hesaplamak için de tabi ki bir algoritmamız var :)

Öncelikle belli bir çözüm kodundaki anlamlı işlemleri sayıyoruz. Çünkü algoritmadaki her cümlenin diğerlerinden bağımsız bir bedeli var, zaman veya alan açısından. Sonra da, bunları kullanarak algoritmanın verimliliğini büyüme fonksiyonları (growth functions) ile göstereceğiz. Anlamlı işlemlere, "d=a+b" gibi atama işlemlerini, yani sabit zamanda uygulanan işlemleri verebiliriz. Bu işlem C1 zamanda uygulanıyorsa, "a=a+1" ise C2 zamanda yerine getiriliyorsa, tahmin edersiniz ki bu iki işlemin ard arda kullanıldığı kod bölümü C1+C2 zaman alacaktır. Başka bir anlamlı işlem ise; koşul ifadeleridir. Yani "if(a<0)" cümlesi de kendince C3 bedeli olan anlamlı bir ifadedir. Aşağıdaki koda bakarsak:

if(a<0)

a=a+1;

else 

d=a+b;

Bu kod ise C3 +(C2 veya C1) zaman alır; çünkü her durumda if satırı işlenecektir, ancak gerisi değişkene bağlıdır. Nitekim t < =C3+max(C2+C1)'dir. Farkındaysanız buraya kadar baktığımız bütün işlem dizileri sabit sürede, daha doğrusu girdi miktarına bağlı olmayan şekilde işlenen ifadeler. İşleri biraz daha karıştırmaya var mısınız? Döngülere geçersek, bir döngünün ne kadar süreceği çoğu zaman başka değişkenlerle belirlidir. Haydi aşağıdaki kod bölümünün zaman hesaplamasını bulmaya çalışalım:

i = 1;   //   C1 zamanda bir kez yapılacak

sum = 0;   //   C2 zamanda bir kez yapılacak

while (i <= n) {   //   C3 zamanda n+1 kez yapılacak; çünkü

// i değişkeninin eşit olma durumunu arıyoruz

i = i + 1;   //   C4 zamanda n kez yapılacak

sum = sum + i;   //   C5 zamanda n kez yapılacak

}

Sonuç olarak bu kod C1+C2+C3*(n+1)+C4*n+C5*n zamanda çalışacak, yani polinomsal yazarak, (C3+C4+C5)*n+(C1+C2+C3) şeklinde n'e bağlı bir denklem elde ediyoruz. Bu da demek ki, Büyük O gösterimini açıklarken kullandığımız C*g(x) fonksiyonu şimdi (C3+C4+C5)*n şeklinde dönüşmüş ve g(x)=n, dolayısıyla O(n) karmaşıklığa sahip bir kodumuz var. Önceki örneklerimiz ise sabit zamanda çalıştığı için O(1) karmaşıklığa sahipti. Genel olarak algoritma analizimizin algoritmasını gözden geçirirsek:

  • Döngüler için çalışma zamanı <= içindeki bütün ifadelerin çalışma zamanları toplamı * döngü sayısı
  • İç içe döngüler için çalışma zamanı <= (en içerde tek bir anlamlı işlem olduğunu varsayarsak) bu tek işlemin çalışma zamanı * tüm döngülerin çalışma zamanları çarpımı
  • Art arda cümleler için çalışma zamanı = cümlelerin çalışma zamanları toplamı
  • Koşullu cümleler için çalışma zamanı <= test cümlesi + yapılacak seçeneklerin maksimumu
  • Birleşik fonksiyonlar için işlemler ise,
    • O(f(x))+O(g(x))=O(max(f(x),g(x)))
    • O(f(x))*O(g(x))=O(f(x)*g(x))
    • O(k*g(x)) veya O(k+g(x)) =O(g(x)) (k!=0)

Diğer Gösterimler

Büyük Omega gösterimi (big ? notation): Büyük O gösterimindeki mantığı anladıysak, diğerleri çok daha kolay olacaktır. Büyük O gösterimindeki g(x) fonksiyonumuz nasıl asimptotik bir üst limit sergiliyorsa, Büyük Omega'daki de bir alt sınır ifade eder. Yani eşitlik bu sefer, x>k sonsuza giderken, f(x)>C*g(x) olur.

Büyük Teta gösterimi (big Θ notation): Büyük O ve Büyük Omega'dan sonra sanırım en kolayı bu olacaktır; çünkü bir g(x) fonksiyonu f(x) olan esas fonksiyonumuz için hem O(g(x))=f(x) şartını, hem de Ω(g(x))=f(x) şartını sağlıyorsa, Θ(g(x))=f(x) şartını da sağlar. Yani algoritmamızın büyüme fonksiyonuna hem alt sınır hem de üst sınır olabilen bir fonksiyon onun sınırıdır, ve Büyük Teta gösterimi kullanılır.

Bunların yanında Küçük O gösterimi ve Küçük Omega gösterimi gibi kullanımlar da vardır, fakat bunlar nadir olarak geçtiğinden üstünde durmayacağız.

Algoritmaların Karşılaştırılması

Algoritmaların analizlerini yaptığımıza ve artık derecelerini bildiğimize göre, bunları büyüme oranlarına göre şekillendirip karşılaştırabiliriz demektir. Büyüme oranlarını girdi miktarını baz alan fonksiyonlarımızla karşılaştırdığımız için, problem boyutu uygulamaya bağlıdır. Mesela hanoi kuleleri probleminde problem boyutu disk sayısıyken, bir sıralama algoritmasında ise bu boyut sıralanacak eleman sayısına eşittir. Yani karşılaştırmak istediğimiz algoritmaları, karşılaştırırken girdi miktarları aynı kabul edilmelidir, bu da aynı değişkeni kullanmakla çözülebilecek bir durumdur. Mesela bu sayıyı n girdi bazında ele alalım, A algoritması 5*n2 zamana ihtiyaç duyuyor, B ise 7*n zamana ihtiyaç duyuyor diyelim. Önemli olan bir spesifik girdi miktarında ne kadar zamanda yaptığı değil, girdi miktarı arttıkça çözmek için gereken zaman nasıl artıyor sorusudur. n=1 durumunda A 5 dakikada, B 7 dakikada çözebilir; fakat n=2, n=3 durumlarında t(A)=20, 405 ve t(B)=14, 21 şeklinde sonuçlar alırız, ki algoritmaların hangisinin daha verimli olduğu apaçık bellidir. İşte bu oransal zaman gereksinimi büyüme oranı olarak bilinir ve iki algoritmanın verimliliğini onların büyüme oranlarını karşılaştırarak bulabiliriz.

Algoritmalar için genel olarak büyüme fonksiyonları:

  • g(x)=c sabit
  • g(x)=log n logaritmik
  • g(x)=log2 n logkare
  • g(x)=n lineer
  • g(x)=n*log n
  • g(x)=n2 karesel
  • g(x)=n3 kübik
  • g(x)=2n üstel

Algoritmaları bu büyüme fonksiyonlarına göre karşılaştırdığımızda, mesela üstel fonksiyon en verimsizidir. Bundan sonra kübik gelir. Çünkü ufak bir girdi değişiminde zaman tüketimi farkları en fazla olan fonksiyonlar bunlardır. En verimlisi ise log n dir; çünkü veriyi sürekli ikiye bölerek kolayca sonuca ulaşır. Bu karşılaştırmalar sonucu programımızı yazarken hangi algoritmanın daha verimli olacağına, en iyi durum, en kötü durum ve ortalama durum analizlerine de ulaşarak karar verebiliriz. En iyi durum analizi, algoritmanın istediği sonuca en kolay ulaşacağı şekilde verinin verildiği zaman hesaplanan karmaşıklıktır. Örneğin bir sıralama algoritmasının karmaşıklığını en iyi durum analizi ile bulmaya çalışıyorsak, bu verinin zaten sıralı verilmesi durumundaki adım sayısına ulaşmakla olur. En kötü durum analizi ise, büyükten küçüğe sıralanacak bir verinin, küçükten büyüğe verildiğinde yapılan hesaplamadır. Ortalama durum ise, verinin tamamen iyi karışmış bir sırada verilmesi gibi, tahmini bir sonuca dayanır.

Algoritmaların karşılaştırılması hakkında daha birçok örnek verilebilir. Tabi ki bunlar için bir algoritmanın zaman ve alan gereksinimleri arasındaki dengenin iyi kurulması gerekir. Ayrıca en başta verdiğim örnekteki gibi, bazı programlar için kodun stili de verimliliğin yanında göze alınması gereken bir etken olabilir. Güzel bir stille yazılmış kod her zaman verimlidir demek ne kadar yanlışsa, zamandan çok da tasarruf eden küçük hileler ile kodu çorba haline getirmek de o kadar yanlış. Kolay okunabilir kodlar ve tekrar kullanılabilir programlar çok daha iyi bir programlamacı davranışı :) Umarım bu yazımızda size algoritmaların analizleri ve karşılaştırılması konusunda gerekli bilgileri sunabilmişizdir, diğer algoritma yazılarımızda görüşmek dileğiyle, programlarınızın karmaşıklığına verimlilik dilerim. :)

Kaynaklar: