İçeriğe geç

Big-O Notasyonu

Bir önceki yazımda algoritma analizinden bahsetmiştim. (Algoritma Analizi) Bu yazımda size orada bahsettiğim Big-O Analizinin kurallarından  ve Big-O ile çalışma zamanı hesapla nasıl oluyor örnekler üzerinden anlatmaya çalışacağım.

İlk olarak kurallardan başlayalım;

BİG-O Analiz Kuralları

1.Katsayı Kuralı: f(N), O(g(N)) ise o zaman k.f(N) yine O(g(N) olur. Yani katsayılar önemsizdir.

2.Toplam Kuralı: f(N),O(h(N)) ise ve g(N),O(p(N)) verilmişse f(N)+g(N) isteniyorsa O(h(N)+p(N)) olur. Bu toplamda sadece üst sınırlar toplanır.

3.Çarpım Kuralı:  f(N),O(h(N)) ise ve g(N),O(p(N)) verilmişse f(N).g(N) degeri için Big-O ; O(h(N).p(N)) olur.

4.Polinom Kuralı: f(N), k dereceli polinom ise f(N) için Big-O; O(N) olur.

5.Kuvvetin Log’u Kuralı: log(Nk) için O(log(N))’dir.

Big-O Yardımıyla Çalışma Zamanı Kestirim Kuralları

1.Looplar(Döngüler):

Bir döngünün çalışma zamanı döngü sayısının bir c sabitiyle çarpımı kadardır.

Döngü n kez çalışacağı için;

Toplam Zaman=c*n olur.

O(N)=n olur. Çünkü katsayılar önemsiz.

Eğer n değeri verilmişse Big-O; O(1) olur.

2.İç İçe Looplar

İçten dışarı doğru her loopun çalışma sayısı dış loopla çarpılırken, sabit değerde çarpıma eklenir.

Toplam Zaman = (İç Döngü)*(Dış Döngü)

Toplam Zaman = (c*n)*(c*n)=c2n2

Katsayı önemsiz olduğu için;

O(N2)

3.Ardışık İfadeler

Her bir ifadenin zaman karmaşıklığı eklenerek tek bir fonksiyon elde edilir.

Toplam Zaman = c0+c1*n+ c2*n2
O(N2) olur. Çünkü polinomlarda derecesi en büyük olan değeri alıyorduk.

4.if-else İfadesi

En kötü çalışma mantığıyla “test bölümü”,”then” veya  “else”  bölümlerinden çalışma zamanı büyük olanla toplanır.

Toplam Zaman = c0+(c3+c4)*n

O(N) olur.

5.Logaritmik Karmaşıklık

Bir algoritma,problemin çözüm kümesini belirli bir sabit oranında bölüyorsa, O(log(N)) zamanına ihtiyaç duyar.

-Loopun k kadar döndüğünü varsayarsak;

*k adımda 2i = n olur.

*Her iki tarafın logu alınırsa i*log2=logn ve

i=logn olur.

Toplam Zaman = O(log(N))’dir.

Peki bu Big-O’nun Avantajları Neler?

  • Sabitler göz ardı edilir.
  • Algoritmalar arasında kıyaslamayı basit ve tek bir değere indirger.
  • Küçük n değerleri göz ardı edilerek sadece büyük N değerlerine odaklanılır.

RAM’den O(N) Dönüşümü

4n2-3nlogn+17n+75

Yukarıda RAM yaklaşımına göre bulunan değeri Big-O ile sadeleştirelim.

İlk olarak katsayılar önemsiz olduğu için katsayıları kaldıralım.

n2-nlogn+n

Daha sonra en büyük dereceli değeri alım.

n2

yani Big-O ‘ya göre çalışma zamanı O(N2) dir.

 

Buraya kadar okuduysanız teşekkür ederim. Faydalı olmuştur umarım. 🙂

 

 

Tarih:GenelYazılım/Teknoloji

İlk Yorumu Siz Yapın

    Bir cevap yazın

    E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir