10
Algoritmaların asimptotik analizinde hangi notasyonlar kullanılır?

Asimptotik analiz sonucunda elde edilen alt ve üst sınırların matematiksel gösterimi için O, Ω, θ olmak üzere üç notasyon kullanılır.

Karmaşıklık
Algoritmaların verimliliğini karşılaştırabilmek için hesaplama karmaşıklığı bulunur. Karşılaştırma yapabilmek için genellikle algoritmanın çalışma süresi ele alınır. Buna zaman karmaşıklığı denir.

Asimptotik analiz
Fakat algoritmaların giriş boyutu n (input) ile geçen süre t arasındaki ilişkiyi tam olarak bulmak imkansız, zor ya da karmaşıktır. Bu nedenle asimptotik analiz tercih edilir.

Üç durum
n ile algoritmanın zaman fonksiyonun büyümesi arasındaki ilişkiyi göstermek için, yani algoritmanın çalışma performansını ifade etmek için genellikle aşağıdaki üç durum (senaryo) geçerlidir:
  • en kötü durum (worst case)
  • en iyi durum (best case)
  • ortalama (average case)
En iyi durum, en az zaman gerektiren; en kötü durum ise en çok zaman gerektiren durumdur. Örneğin bir dizide aranan değerin dizinin ilk elemanı olması en iyi senaryo dizide aranan elemanın hiç bulunmaması ise en kötü senaryodur.

Üç notasyon
Bir algoritmanın çalışma süresinin, algoritmanın girdilerinin bir fonksiyonu olarak hesaplanması ve bu sonucun gösterilmesi için üç tür notasyon (notation) kullanılır: Söz konusu notasyonlar, asimptotik analiz sonucunda çizilen alt ve üst sınırların matematiksel gösterimi için kullanılır.


 
Ο notasyonu
O notasyonu, en kötü durumda asimptotik üst sınırı (asymptotic upper bound) göstermek için kullanılır.

Ω notasyonu
O notasyonu, en iyi durumda asimptotik alt sınırı (asymptotic lower bound) göstermek için kullanılır.

θ notasyonu
θ notasyonu programın (algoritmanın) çalışması için gerekli ortalama süreyi göstermek için kullanılır.

Grafik
Aşağıdaki grafiklerde f(n) ile sırasıyla O, Ω, θ olmak üzere g(n) arasındaki ilişkiler gösterilmiştir.
 
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)

Henüz yorum yapılmamış.

İlgili Konu
Algoritma Analizi
İlgili Kayıtlar
İlginizi Çekebilir