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

1. ZAMAN KARMAŞIKLIĞI (TIME COMPLEXITY)
Time Complexity , 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.

Ö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 zaman karmaşıklığı ; T(n) = (2n+2) + n + 1 + 1 = 3n + 4

ÖRNEK – 2

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

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

      for( k=1 ; k<n ; k++) // 'k=1' -> 1 kez , 'k<n' -> n kez , 'k++' -> n-1 kez çalışacaktır. Toplam 2n
        if(A[k]<enkucuk)    //  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 zaman karmaşıklığı ; 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<n  ; i++ )  // 'i=0' -> 1 kez çalışacak, 'i<n' -> n+1 kez çalışacak , i++ -> n kez çalışacak. Toplam : 2n+2
        for( j=0 ; j < m ; j ++) // 'j=0' -> 1 kez çalışacak, 'j<m' -> 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 zaman karmaşıklığı ; 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 zaman karmaşıklığı ; T(n) = 2n

 

2. BIG O NOTASYONU
  Big o notasyonu fonksyonların input size’ı büyüdükçe oluşacak karmaşıklığı göstermek için kullanılır. Fonksyonun input size’ı büyüdükçe küçük kalan big o notasyonu makbüldür. Eğer input size ile beraber big o da çok fazla büyüyorsa var ise alternatiflerini kullanmamız gerekir.

   Big o bulunurken time complexity bağıntısındaki en büyük artışı yöneten terim alınır diğerleri göz ardı edilir çünkü input size sonsuza giderken bu büyümeyi yönetecek olan en büyük değişkenli derimdir.

Time complexity’de büyümeyi yöneten terimi seçeceğimi 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.

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


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)

Bir kaç örnek daha ;
𝑓(𝑛) = 107𝑛^0.6 + 𝑛^3 𝑙𝑜𝑔 (𝑛5) + 𝑛𝑙𝑜𝑔(𝑛4) + 0.1𝑛^3   -> O(𝑛^3)

3. 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 yahut 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 );
}

Another example

// Here c is a constant greater than 1   
for (int i = 2; i <=n; i = pow(i, c)) { 
   // some O(1) expressions
}

Exponential Zamanlı : O(2^N) 

input size büyüdükçe baya yavaşlar if N = 1000.000, T(N) would be 21000.000. Örneğin :Brute Force algorithm

Factorial Zamanlı : O (N!)

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