Bu eğitimde asimptotik notasyonların ne olduğunu öğreneceksiniz. Ayrıca, Big-O notasyonu, Theta notasyonu ve Omega notasyonu hakkında bilgi edineceksiniz.
Bir algoritmanın verimliliği, algoritmayı yürütmek için gereken süreye, depolamaya ve diğer kaynaklara bağlıdır. Verimlilik, asimptotik notasyonlar yardımıyla ölçülür.
Bir algoritma, farklı giriş türleri için aynı performansa sahip olmayabilir. Giriş boyutunun artmasıyla performans da değişecektir.
Girdi boyutunun sırasındaki değişiklik ile algoritmanın performansındaki değişimin incelenmesi asimptotik analiz olarak tanımlanmaktadır.
Asimptotik Gösterimler
Asimptotik gösterimler, girdi belirli bir değere veya sınırlayıcı bir değere yöneldiğinde bir algoritmanın çalışma süresini açıklamak için kullanılan matematiksel notasyonlardır.
Örneğin: Kabarcık sıralamasında, giriş dizisi zaten sıralandığında, algoritma tarafından alınan zaman doğrusaldır, yani en iyi durumdur.
Ancak, girdi dizisi ters durumda olduğunda, algoritma, öğeleri sıralamak için maksimum süreyi (ikinci dereceden), yani en kötü durumu alır.
Girdi dizisi sıralanmadığında veya ters sırada olmadığında, ortalama süre alır. Bu süreler, asimptotik gösterimler kullanılarak belirtilmiştir.
Esas olarak üç asimptotik gösterim vardır:
- Big-O gösterimi
- Omega notasyonu
- Teta gösterimi
Big-O Notasyonu (O-notasyonu)
Big-O gösterimi, bir algoritmanın çalışma süresinin üst sınırını temsil eder. Böylece, bir algoritmanın en kötü durum karmaşıklığını verir.
Big-O, bir fonksiyonun üst sınırını verir
O (g (n)) = (f (n): pozitif sabitler vardır c ve n 0 öyle ki tüm n ≧ n 0 için 0 ≦ f (n) ≦ cg (n )
Yukarıdaki ifade, yeterince büyük olması için ve arasında uzanacak şekilde pozitif bir sabit varsa , bir fonksiyon f(n)kümeye ait olarak tanımlanabilir .O(g(n))c0cg(n)n
Herhangi bir değeri için n, bir algoritmanın çalışma süresi, tarafından sağlanan süre ile kesişmez O(g(n)).
Bir algoritmanın en kötü durumdaki çalışma süresini verdiğinden, her zaman en kötü durum senaryosuyla ilgilendiğimiz için bir algoritmayı analiz etmek için yaygın olarak kullanılır.
Omega Notasyonu (Ω-notasyonu)
Omega gösterimi, bir algoritmanın çalışma süresinin alt sınırını temsil eder. Böylece, bir algoritmanın en iyi durum karmaşıklığını sağlar.
Omega, bir fonksiyonun alt sınırını verir
Ω (g (n)) = (f (n): pozitif sabitler vardır c ve n 0 öyle ki tüm n ≧ n 0 için 0 ≦ cg (n) ≦ f (n )
Yukarıdaki ifade, yeterince büyük olması için yukarıda yer alan pozitif bir sabit varsa , bir fonksiyon f(n)kümeye ait olarak tanımlanabilir .Ω(g(n))ccg(n)n
Herhangi bir değer için n, algoritmanın gerektirdiği minimum süre Omega tarafından verilmektedir Ω(g(n)).
Teta Gösterimi (-gösterimi)
Teta gösterimi, işlevi yukarıdan ve aşağıdan kapsar. Bir algoritmanın çalışma süresinin üst ve alt sınırını temsil ettiğinden, bir algoritmanın ortalama durum karmaşıklığını analiz etmek için kullanılır.
Theta, işlevi sabit faktörler içinde sınırlar
Bir fonksiyon için g(n), Θ(g(n))aşağıdaki denklem ile verilir:
Θ (g (n)) = (f (n): pozitif sabitler var c 1 , c 2 ve n 0 öyle ki 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) hepsi için n ≧ n 0 )
Yukarıdaki ifade, bir fonksiyonu olarak tanımlanabilir f(n)setine Θ(g(n))pozitif sabitleri mevcut ise ve bu arasına sıkıştırılan şekildedir ve yeterince büyük bir n için.c1c2c1g(n)c2g(n)
Bir fonksiyon ise f(n)ikisinin ortasında yalanlar ve herkes için , daha sonra asimptotik sıkı bağlı olduğu söylenir.c1g(n)c2g(n)n ≧ n0f(n)
