1 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:
Üç 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:

Ο 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.

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)
Üç 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:
- Ο (Oh) notasyonu
- Ω (Omega) notasyonu
- θ (Theta) 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ış.