Big O Notasyonu

  Kısaca sınav öncesi bir tekrar adına yazayım dedim.

Şimdi şöyle bir metodumuzun olduğunu düşünelim;

 public void deneme(int x, int y) {

  x = 6;
  y = 4;
 }

burada her işlem birer kez yapılıyor. İki değişkeni de bir değere atamak her biri için birer atamadır. Bundan dolayı buna O(1) diyoruz.

Eğer şöyle bir metod olsaydı;

 
 public void deneme2(int x, int y, int[] dizi) {

  x = 6;
  y = 4;

  for (int i = 0; i < dizi.length; i++) {
   System.out.println(dizi[i]);
  }

 } 

burada ise metodumuzdaki println metodu dizi boyutuna kadar (bilmediğimiz için n diyelim) çalışacaktı. Buna da O(n) diyoruz.

Kısacası bir kod parçasının (metod vs.) tekrarları yoksa O(1) varsa metodun kaç kere yapılacağını belirleyen değer(x)   O(x) olur. Tabii burada hep en kötü durumdan bahsediyoruz.

Bir tane de logn'li duruma örnek verelim. Mesela binary search, her defasında diziyi ikiye bölüyoruz. Mesela dizinin boyutu N olsun.
Birinci defada N/2
İkinci defada   N/4
Üçüncü defada N/8 .... en sonunda  N/N e kadar gidecek. (Aslında aradığımız eleman dizinin ortasında olup  metodun ilk çalışmasında sayıyı bulabiliriz ama burada en kötü durum notasyonundan (Big O) bahsettiğimiz için işlemleri sonunda kadar yapmamız lazım.)

Gördüğümüz gibi bölümler hep 2'nin kuvvetleri.  O zaman N/N  de  alttaki N'in  2^k gibi bir değere eşit olması lazım.

2^k = N  ifadesinden   k yı çekersem  log 2 tabanında N olur. Yani  bu metod logN kez dönecek diyebiliriz.  O zaman Big O notasyonu da O(logn) olur.

Time Complexity'nin Big-O Gösterimi
Burada hiç formüllere girmeden basit halini anlatacağım.
T(n) 'li denklemden Big-O bulmak için ise  denklemdeki en yüksek dereceli terim alınır.

Örneğin T(n) = 4n^2 + 2n + 7 şeklinde bir denklemimiz olsun. Burada en yüksek dereceli terim n^2 dir. O zaman bu denklemin Big-O 'su  O(n^2) dir.