Büyüme Hızı ve Büyük-O(big-O)notasyonu

1. Büyüme hız bir algoritmanın performansını yansıtan en iyi göstergedir.
   
2. Büyük-O notasyonu büyüme hızını gösterir. Bir algoritmanın performansını en iyi tanımlayan matematiksel bir formüldür ve algoritmanın iç detaylarına bakılarak elde edilir.
3. Büyük-O girdi verisinin büyüklüğünü gösteren bir N parametresine dayanan bir fonksiyondur.
4. Örneğin n değerine bağlı olarak performansı (sabit a, b, c değerleri için) an2 + bn + c olan bir algoritmanın performansı O(N2)’dir
5. N değeri arttıkça N2 terimi baskın olacağı için büyük-O notasyonunda sadece baskın olan terim kullanılır

 

O Notasyonu- Asimtotik Üst Limit 

Bir algoritmanın çalışma süresi
   T(N)=O(f(n))

• T(N)  c f(n)  ve N  n0 koşullarını sağlayan c ve n0 değerleri varsa T(N)  c f(n)  ifadesi doğrudur.
• f(n), T(N)’in asimtotik üst limiti olarak adlandırılır.
• T(N)=O(f(n))
  
  

  O Notasyonu

   O notasyonunda yazarken en basit şekilde yazarız.
  Örneğin
  3n2+2n+5 = O(n2)
  Aşağıdaki gösterimlerde doğrudur fakat kullanılmaz.
  3n2+2n+5 = O(3n2+2n+5)
  3n2+2n+5 = O(n2+n)
  3n2+2n+5 = O(3n2)
  
  Bir programın asıl çalışma zamanını hesaplama (örnek)
  Bir işlem için harcanan zaman 10ms olsun(bir veri üzerinde yapılan tek bir işlem)
  1000 veriyi işlemek için programın ne kadar çalışması gerekir? Programın çalışma zamanı aşağıdaki gibi verilmişse bu değer nasıl hesaplanır?
  log10 N
  N
  N log10 N
  N2
  N3
  
  (1 veri için zaman) x (N veri için verilen büyük-O( ) zaman karmaşıklığı)