0 00
 |
Büyük O nostasyonu ile algoritmaların asimptotik analizi arasındaki ilişki nedir? |
Büyük O notasyonu, algoritmaların zaman karmaşıklığının büyüme fonksiyonunu analiz etmek için kullanılır.
Asimptotik analiz
Algoritmaların asimptotik analizi, algoritmanın çalışma performansının sınırlarını matematiksel olarak göstermeye yarar.
Örneğin bir algoritmanın çalışma süresi fonksiyonu T1(n) diğeri ise T2(n2) ise, ilk fonksiyonun çalışma süresi girdilere nazaran doğrusal, ikincisi ise eksponansiyel olarak artar. Küçük n değerleri için iki fonksiyonun çalışma süreleri yakın, büyük n değerleri için belirgin derecede farklı olacaktır.
Büyük O notasyonu
Büyük O notasyonu, bir algoritmanın çalışma süresinin üst değerini (asymptotic upper bound), algoritmanın en kötü durumdaki (worst-case) zaman karmaşıklığını ölçmek için kullanılır.
Gösterim
Bu durumda f(x) ile g(x) arasındaki ilişki şöyle ifade edilir:
Yani n0'dan büyük bütün n değerleri için O(f(n)) = O(g(n)) olur. Grafikte de gösterildiği gibi O nostasyonu, ilgili fonksiyonun üst sınırının göstergesidir.
Örnek
f(x) = 2x2+3x+9 fonksiyonu için zaman karmaşıklığının büyük O notasyonunun O(n2) olduğunu gösteriniz.
Yorum
n0'dan büyük her n değeri (n ≥ n0) için g(x) = 14x2 fonksiyonu her zaman f(x) = 2x2+3x+1'ten daha büyüktür. Yani n0>1 için f(x) hiçbir zaman g(x)'i geçemez. Bu da f(x)'in üst sınırını gösterir.
Algoritmaların asimptotik analizi, algoritmanın çalışma performansının sınırlarını matematiksel olarak göstermeye yarar.
Örneğin bir algoritmanın çalışma süresi fonksiyonu T1(n) diğeri ise T2(n2) ise, ilk fonksiyonun çalışma süresi girdilere nazaran doğrusal, ikincisi ise eksponansiyel olarak artar. Küçük n değerleri için iki fonksiyonun çalışma süreleri yakın, büyük n değerleri için belirgin derecede farklı olacaktır.
| n | T1(n) | T2(n2) |
| 1 | 1 | 1 |
| 2 | 2 | 4 |
| 3 | 3 | 9 |
| 10 | 10 | 100 |
| 1000 | 1000 | 1.000.000 |
Büyük O notasyonu
Büyük O notasyonu, bir algoritmanın çalışma süresinin üst değerini (asymptotic upper bound), algoritmanın en kötü durumdaki (worst-case) zaman karmaşıklığını ölçmek için kullanılır.
f(n)>0 ve g(n)>0 fonksiyonlarında n≥ n0 için öyle bir c>0 vardır ki f(n) ≤ c.g(n) olur. Her n için bu koşulları sağlayacak c ve n0 değerleri varsa f(n) fonksiyonunun zaman karmaşıklığı g(n) fonksiyonunkine eşittir, denir.
Gösterim
Bu durumda f(x) ile g(x) arasındaki ilişki şöyle ifade edilir:
| O(f(x) = O(g(x)) ya da f(x) ∈ O(g(x)) |
Yani n0'dan büyük bütün n değerleri için O(f(n)) = O(g(n)) olur. Grafikte de gösterildiği gibi O nostasyonu, ilgili fonksiyonun üst sınırının göstergesidir.
Örnek
f(x) = 2x2+3x+9 fonksiyonu için zaman karmaşıklığının büyük O notasyonunun O(n2) olduğunu gösteriniz.
| c | fonksiyon | n0=1 | n=2 | n=3 | .. | n=50 |
| f(x) = 2x2+3x+1 | 6 | 12 | 22 | .. | 5151 | |
| c=1 | g(x) = x2 | 1 | 4 | 9 | .. | 2500 |
| c=14 | g(x) = 14x2 | 6 | 56 | 126 | .. | 35000 |
Yorum
n0'dan büyük her n değeri (n ≥ n0) için g(x) = 14x2 fonksiyonu her zaman f(x) = 2x2+3x+1'ten daha büyüktür. Yani n0>1 için f(x) hiçbir zaman g(x)'i geçemez. Bu da f(x)'in üst sınırını gösterir.
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)
Henüz yorum yapılmamış.
