Mustafa Çağatay KIZILTAN

1. Zaman Karmaşıklığı ve Büyük O Notasyonu (Time Complexity and Big-o Notation)

1. YÜRÜTME ZAMANI (Running Time)

Yürütme zamanı yani Running time , bir programın ya da fonksiyonun işlevini tam anlamıyla yerine getirebilmesi için her işlemden kaç kere yapması gerektiğini gösteren bir bağıntıdır. Running time’ın detaylarına girmeden önce bir de baz alınan temel işlem birimi kavramından bahsetmemiz gerekiyor. Temel işlem birimi ise hesaplama yaparken hangi statementların baz alınacağıdır.

Running time hesaplaması yapılırken temel işlem birimi execute edilen her bir statement olarak kabul edilir.  Bu da bize ilgili fonksiyonun ya da programın gerçek çalışma zamanına yakınsayabileceğimiz bir bağıntı verir. Running time hesaplarken yukarıda da söylediğim gibi her bir statementin kaç kez çalışacağını hesaplar ve toplarız. Yani yürütme zamanı bize kesin bir süre vermez. Bunun yerine girdi boyutuna bağlı bir bağıntı verir.

Peki ozaman running time’ı nerede kullanabiliriz? Running time bağıntısına bakarak algoritmamızın farklı bilgisayarlarda nasıl davranacağını kestirebiliriz. Ancak gerçeğe yakın sonuçlar da elde etsek, gerçek sonuçlar elde edemeyiz. Bunun sebepleri ise, running time hesabı yapılırken, toplama, bölme, mod alma vs gibi tüm işlemleri eşit sürede gerçekleşiyor yani 1 birimlik cost’a sahip olarak kabul ederiz ancak bu pratikte doğru değildir.

Aşağıda farklı fonksiyonlar için running time hesaplaması yapılmıştır. Yapılan iş, her bir executing statement’i temel işlem birimi olarak kabul ederek, her birinin kaç kez çalıştığını hesaplamaktır.

ÖRNEK-1

 float bulOrta(float A[ ] , int n)
 {

    float ortalama toplam=0;
    int k;

     for(k=0 ; k < n ; k++)  // k=0 -> 1 kez , k < n -> n+1 kez , k++ -> n kez çalışacaktır. Toplam 2n+2
       toplam += A[ k ];     // Döngü n kez döneceği için bu ifade n kez çalışacaktır

     ortalama = toplam / n;  // 1 kez çalışacaktır.
  
   return ortalama;          // 1 kez çalışacaktır.
 }

Yukarıdaki kodun toplam running time’ı ; T(n) = (2n+2) + n + 1 + 1 = 3n + 4

2. BEST- AVERAGE – WORST CASE

Best case kodun çalışabileceği en ideal süredir. Örneğin, bir dizi üzerinde arama işlemi yapıyorsak, aradığımız verinin dizinin ilk elemanı olması sonucu elde edeceğimiz sonuç best casedir. Ancak biz yazılım mühendisleri olarak kodumuzun her durumda maksimum performansla çalışması için, worst case üzerine kafa yorar hesaplarımızı da bunun üzerinden yaparız. Yine bir dizi üzerinde arama işlemi yapıyorsak, aradığımız verinin dizide hiç bulunmaması bizim için worst case’dir. Bu sebeple Running time ve Time complexity hesaplarken de, girmesi muhtemel tüm if’lere giriyormuşçasına worst case üzerinden hesaplamalarımızı yaparız. Average case ise çoğunlukla karşılaşacağımız durumdur. Best case ile worst case’in ortalaması.

ÖRNEK – 2

   float bulEnkucuk(float A[ ])
   {
      float enkucuk;
      int k;

      enkucuk = A[0];        //1 kez çalışacaktır.

      for( k=1 ;k// 'k=1' -> 1 kez , 'k < n' -> n kez , 'k++' -> n-1 kez çalışacaktır. Toplam 2n
        if(A[k]//  n-1 kez çalışacaktır
            enkucuk = A[k];  // worst case'den hareketle n-1 kez çalışacaktır

      return enkucuk;        //1 kez çalışacaktır.
    }

Yukarıdaki kodun toplam running time’ı ; T(n) = 1 + 2n + n-1 + n-1 + 1 = 4n 

ORNEK-3

void toplaMatris(matris A, matris B, matris c)
{
    int i,j;
  
      for( i=0 ; i//i=0 -> 1 kez çalışacak, i n+1 kez çalışacak , i++ -> n kez çalışacak. Toplam : 2n+2, döngü ise n kez dönecek.
        for( j=0 ; j < m ; j ++)  //'j=0' -> 1 kez çalışacak, 'j m+1 kez çalışacak , i++ -> m kez çalışacak. Toplam :  n(2m+2)
           c[ i ][ j ] = A[ i ][ j ] + B [ i ][ j ];  // n.m kez çalışacak
}

Yukarıdaki kodun toplam running time’ı ; T(n,m) =(2n+2) + n(2m+2) + n.m = 3.m.n + 4.n + 2

ORNEK-4 : Rekürsif fonksyon için T(n)

 ...int faktoriyel(int n){

        if(n <=1)      // n elemanli bir işlem için n kez sorgu yapar.
          return 1;    // rekürsifliğin bittiği durumda çalışan son çağrı olduğu için tek bir kez çalışır ve işlem biter : 1
        else    
          return (n*faktoriyel(n-1));  // n-1 kez çalışır

   }

Yukarıdaki kodun toplam running time’ı ; T(n) = 2n

3. ZAMAN KARMAŞIKLIĞI(Time Complexitiy) ve BIG O NOTASYONU

Zaman karmaşıklığı ise fonksiyonumuza gelen girdi sayısı çok büyüdüğünde, teoride sonsuza giderken fonksiyonumuzun nasıl davranacağını asimptotik notasyonlar ile gösteren gösterimdir.  Eğer input size ile beraber big o sonucu da çok fazla büyüyorsa ise fonksiyon verimsizdir diyebiliriz. Fonksiyonun input size’ı büyüdükçe küçük kalan big o notasyonu makbüldür.  

Big o bulunurken running time bağıntısındaki en büyük katsayılı diğer bir deyişle artışı domine eden baskın terim alınır diğerleri terimler de göz ardı edilir çünkü input size sonsuza giderken bu büyümeyi yönetecek olan en büyük değişkenli terimdir. 

n !  > 2^n  >  n^3  >  n^2  >  nlogn  >  n  > logn  >  1 

Time complexity’de büyümeyi yöneten terimi seçeceğimiz için bağıntı içerisinde en çok karşımıza çıkan değişken terimlerin sıralamasını aşağıda hazır olarak verdim. Eğer ki bu terimler aynı bağıntı içerisindeyse yapmanız gereken seçim en büyük olanı seçmektir. Diğer bir kural ise seçilen en büyük derime ait çarpan, bölen, toplanan, çıkarılan sabitleri yok saymaktır çünkü bunlar da sonsuza giden büyüme sırasında anlamını kaybedecektir.

Yukarıdaki örnekler için Time complexity üzerinden Big o notasyonlarını bulalım.

ORNEK-1    T(𝑛) = 3𝑛 + 4  -> O(n)
ORNEK-2    T(𝑛)  = 4𝑛  -> O(n)
ORNEK-3    T(𝑛,m) = 3.m.n + 4.n + 2  -> 3.𝑛.𝑛 + 4𝑛 -> O(𝑛^2)
ORNEK-4    T(𝑛) = 2𝑛   -> O(n)

ORNEK-5 (Ek örnek)
𝑓(𝑛) =  107 𝑛^0.6  +  𝑛^3  𝑙𝑜𝑔 (𝑛5)  +  𝑛𝑙𝑜𝑔 (𝑛4)  +  0.1 𝑛^3   –>  O(𝑛^3)

4. BAZI KALIPLARIN BIG-O NOTASYONUNUN KOLAY YOLDAN BULUNMASI

Sabit Zamanlı : O (1)

İfadenin çalışma zamanı input size N’e bağlı değildir. Örneğin;

  • Dizi üzerinden elemana ulaşmak
  • Sabit boyutlu stackten push ve pop işlemi yapmak
  • Aritmatik operasyonlar
  • Kıyaslamalar
if(a>b)
	statement;
else
	statement;

Linear Zamanlı : O (N)

Çalışma zamanı direkt olarak input size N’e bağldır. Yani input size büyüdükçe çalışma zamanı da büyür. Örneğin;

  • Linear dizide eleman aramak
  • Linear dizide traversal işlemler
  • Linear arrayda max ve min bulma
for ( i = 0; i < N; i++ )
     statement;

Quadratic Zamanlı: O (N^2)

Eğer input size’ı N’e bağlı iç içe iki for döngü var ise bu quadratic zamanlı çalışır.  Çalışma zamanı N * N olarak artar.

  • Insertion sort
  • Bubble sort
  • Selection Sort
for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

Cubic Zamanlı : O (N^3)

Eğer input size’ı N’e bağlı iç içe üç for döngü var ise bu quadratic zamanlı çalışır.  Çalışma zamanı N * N * N olarak artar.

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ ){
	for ( j = 0; j < N; j++ )
            statement;
	}
}

Logarithmic Zamanlı : O (log N)

Bir loopun time complexity’si ya da big o notasyonu, loopun değerleri bir sabit tarafından bölünüp çarpıldığı zaman O(log N) olur.

   O(log N)  O(N)’den daha hızlıdır.

Örneğin : Binary Search

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

O (N log N)

Eğer bir loop değişkeni sabit üssel tarafından artırılıyor ya da azaltılıyorsa burada O(NlogN) karmaşıklığından bahsedilebilir.

Örneğin : Quick Sort

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Exponential Zamanlı : O(2^N) 

input size büyüdükçe çokça yavaşlar. Örneğin :Brute Force algorithm

Factorial Zamanlı : O (N!)

EN YAVAŞI !!!
Örneğin : Travel Salesman Problem (Gezgin satıcı problemi)