İçeriğe geç

Ay: Ekim 2016

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.

Yorum Bırak

Algoritma Analizi

Algoritmanın sahip olması gereken özellikler

  • Giriş/Çıkış bilgisi
  • Sonluluk
  • Kesinlik
  • Etkinlik
  • Başarım ve Performans

Algoritmaların Analizi

Aynı problemi birçok algoritma ile çözebiliriz ancak bizim için önemli olan verimliliktir. Bu nedenden dolayıda algoritmalar arasında bir kıyaslama yaparız. Bu kıyaslama genel olarak “Çalışma Zamanı”ın karşılaştırılmasıdır.

Çalışma Zamanı Analizi(Karmaşıklık Analizi) bir algoritmanın artan veri girişine bağlı olarak işleme zamanındaki değişikliğin tespit etmektirç

Kullanılacak Yöntemler

1.Deneysel Analiz Yöntemi

  • Örnek problemlerde denenmiş bir algoritmada hesaplama deneyimine dayanır.
  • Amaç; pratikte algoritmanın nasıl davrandığını tahmin etmektir.
  • Program yazılır ve problem örneklerinin bazı sınıfları üzerinde performans test edilir.
  • Bilimsel yaklaşımdan çok uygulamaya yöneliktir.
4 Yorum