YAZILIMIN HESAPLAMA KARMASIKLIGI

Yazan:Fatih KABAKCI

Bir yazılımın hesaplama karmaşıklığı(computational complexity), bir algoritma, prosedür, fonksiyon veya bir metodun işletilmesi için harcanan CPU zamanı(time) ve/veya kaplanan bellek(memory) ihtiyacını belirten ve aynı zamanda ilgili algoritmanın ölçeklenebilirliğini(scability) ifade eden bir kavramdır. Bir algoritmanın performansı(performance), algoritmanın çalışması için harcanan CPU zamanı ile ihtiyaç duyduğu bellek alanı ile ilgilidir. Bir algoritmanın ölçeklenebilirliği(scalability) ise, problemin boyutunun artması ile algoritma çözümü ve anlamlandırılmasının ne derece değiştiği ile ilgilidir.

Genel olarak Bilgisayar Bilimlerinde bir algoritmanın performans ve karmaşıklık analizi yapılırken CPU ve bellek konusu gözetilir. Bunun daha açılmış hali kimi yayınlarda, CPU zamanı, disk alanı, hafıza alanı ve network kullanımı olarak bahsedilir.

Bir algoritma analizinde genel olarak aşağıdaki 3 senaryo sorgulanır.

En kötü durum(worst case): Bir kod parçasının işletilmesi sırasında harcanan maksimum zaman ve/veya kaplanan maksimum bellek ihtiyacını gösterir.
En iyi durum(best case): Bir kod parçasının işletilmesi sırasında harcanan minimum zaman ve/veya kaplanan minimum bellek ihtiyacını gösterir.
Ortalama durum(average case): Bir kod parçasının işletilmesi sırasında harcanan ortalama zaman ve/veya kaplanan ortalama bellek ihtiyacını gösterir.

Örneğin Doğrusal Arama(Linear Search) algoritmasının performansına bakarak aşağıdaki dizideki bir elemanı bulmaya çalışalım.

örnek olarak 6 elemanlı, 8 12 90 13 2 7 sayılarından oluşan bir dizimiz olsun. Doğrusal arama algoritmasına göre bu sayılar arasında bulunacak bir eleman için en kötü durum; elemanın en sonda bulunması veya hiç dizide olmamasıdır. Bu durumda en çok 6 arama yapılacağı için n=6 worst case durumu oluşur [ O(n) ]. en iyi durum; elemanın en başta bulunmasıdır. Bu durumda 1 arama yapılacağı için n=1 best case durumu oluşur [ O(1) ]. ortalama durum; elemanın bir çok kez aramada ortalama olarak kaç adımda bulunacağını gösterir. Bu durumda her bir elemanın eşit derece de aranması n=6/2=3 average case durumu oluşur[ O(n/2) ]. Aynı şekilde kaplama alanına bakıldığında dizi uzunluğu sabit olduğu için bu algoritma da tüm senaryolar eşittir.

Yazılımın hesaplama karmaşıklığı belirlenirken harcanan CPU zamanı bazı kod ifadelerine göre değişik şekillerde belirlenir. Aşağıda farklı kod ifadeleri ile hesaplama örnekleri verilmektedir.

Sıralı İfadeler(Sequence of Statements)

Sıralı ifadeler, sıralı olarak ard arda işletilen kodlara verilen isimdir. Her bir ifadenin CPU zamanı doğrusal olarak toplanarak ilgili algoritma ya da kod parçacığının hesaplama karmaşıklığı ortaya çıkarılır.

statement 1;
statement 2;
...
statement n;

total time = time(statement 1) + time(statement 2) + ... + time(statement n)

Elde edilen toplam zaman sabit olduğu için O(1) ile ifade edilir.

Dallanmalar - Kontrol Deyimleri(If-Then-Else)

Dallanmalar, farklı durumlarda farklı kollardan devam eden kod parçalarına verilen isimdir. Her bir dal parçasının CPU zamanı ayrı ayrı hesaplanarak maksimum değer elde edilir. Bu değer en kötü durumu(worst case) ihtiva eden hesaplama karmaşıklığını verir.

if (cond) then
block 1 (sequence of statements)
else
block 2 (sequence of statements)
end if;

max(time(block 1), time(block 2))

Örneğin elde edilen maksimum zaman block1 için O(1), block2 için O(n) olursa, algoritmanın hesaplama karmaşıklığı O(n) olarak hesaplanır.

Döngüler(Loops)

Döngüler, bir kod bloğunu belirli bir koşul dahilinde tekrar tekrar çalıştıran ifadelere denir. Döngü bloğunun çalıştırdığı her ifade ayrı ayrı hesaplanarak tekrar sayısı ile çarpılır. Bu durumda ayrı olarak çalışan her ifade için O(1), denilirse, n kez çalıştırma O(1) * n, bu da O(n) hesaplama karmaşıklığını oluşturur.

for I in 1 .. n loop
sequence of statements
end loop;

İç İçe Döngüler(Nested Loops)

İç içe döngüler, tekrar tekrar çalıştırılan bir kod bloğunu kapsayan bir döngünün, başka bir döngü ile yine tekrar tekrar çalıştırılmasına denir. Örneğin m ve n uzunluğuna sahip iki iç içe döngü, bir kod bloğunu n * m kez çalıştıracaktır. O(1) olarak çalışan bir kod bloğu, O(1) * n * m olacak şekilde, O(n * m) hesaplama karmaşıklığına sahiptir.

for I in 1 .. n loop
      for J in 1 .. m loop
      sequence of statements
   end loop;
end loop;

Fonksiyonlar(Functions)

Fonksiyonlar, prosedürler ve/veya metotlar, belirli isimler dahilinde kod bloklarını barındıran, çağrılabilir ve değer döndürebilir alt rutinlere verilen addır. Bu yapıların hesaplama karmaşıklığını, içerisinde barındırdığı kodların hesaplama karmaşıklığı oluşturur.