Algoritmaları karşılaştırabilmek için bir algoritmanın zorluk derecesi ölçümüne “Computational Complexity” denir. Aslında problem veya algoritmaların çözüme ulaşmadaki karmaşıklığını ölçmek için kullanılır.Fonksiyon içerisindeki önemsiz kısımlar ve katsayılar atılarak basitleştirilir ve gerçek fonksiyona göre yaklaşık bir değer bulunur. Elde edilen bu yeni etkinlik ölçümüne “Asymptotic Complexity” denir.
Bunun üç türünü göreceğiz: büyük- \Theta Θ gösterimi, büyük-O gösterimi, ve büyük- \Omega Ω gösterimi.
Büyük-O gösterimi: Algoritmanın çalışabileceği en yüksek üst sınırı ifade eder.Yani bu üst sınırdan daha kötü çalışamayacağını gösterir.
Asymptotic upper bound
-f(n) = O(g(n)), eğer sabit bir c ve n0 değeri için
-f(n) >= c.g(n) bütün n >= n0 değerleri için doğruysa
-f(n) ve g(n) pozitif değere sahip fonksiyonlardır.
Örneğin; T(n)=3n²+8n+3 için O(n²) olduğunu gösterelim.
T(n)=3n²+8n+3 g(n)=n²
c.g(n) >= 3n²+8n+3
c.n² >= 3n²+8n+3
3n²+8n²+3n² >= 3n²+8n+3
14n² >= T(n)
n0=1 c=14
Büyük- \Omega Ω :Bazen, üst sınır belirlemeden, bir algoritmanın en az belirli bir süre aldığını söylemek isteriz. Bu durumda büyük-Ω gösterimini kullanırız.
Asymptotic Lower Bound
-f(n) = W (g(n)), eğer sabit bir c ve n0 değeri için
-c.g(n) <= f(n) bütün n >= n0 değerleri için doğruysa
Örneğin; T(n)=4n³+2n²+3 için O(n³) olduğunu gösterelim.
T(n)=4n³+2n²+3 g(n)=n³
c.g(n) <= 4n³+2n²+3
c.n³ <= 4n³+2n²+3
4n³ <= T(n)
Katsayılar atıldığında O(n³) bulunur.
Büyük- \Theta Θ gösterimi:Büyük-Θ gösterimi kullandığımızda, çalışma süresinin üzerinde asimptotik olarak sıkı bir sınır vardır diyebiliriz. "Asimptotik olarak" çünkü sadece n'nin yüksek değerleri için önemlidir. "Sıkı sınır" deriz; çünkü çalışma süresini üstten ve alttan sabit bir çarpana kadar indirebildik.
Asymptotic tight bound
-f(n) = Θ(g(n)), eğer sabit c1, c2, ve n0, değerleri için
-c1.g(n) <= f(n) <= c2.g(n) bütün n >= n0 değerleri için doğruysa
Örneğin;T(n)=2n²+3n+1 için O(n²) olduğunu gösterelim.
T(n)=2n²+3n+1 g(n)=n²
c1.g(n) <= 2n²+3n+1 <= c2.g(n)
c1.n² <= 2n²+3n+1 <= c2.n²
2n² <= 2n²+3n+1 <= 6n²
c1=2 c2=6 n0=1
