En kötü durum analizi (Worst Case Analysis)
Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde bir algoritmanın incelenmesi sırasında sıkça kullanılan bu terim çalışmakta olan algoritmanın en kötü ihtimalle ne kadar başarılı olacağını incelemeye yarar.
Bilindiği üzere bilgisayar bilimlerinde yargılamalar kesin ve net olmak zorundadır. Tahmini ve belirsiz karar verilmesi istenmeyen bir durumdur. Bir algoritmanın ne kadar başarılı olacağının belirlenmesi de bu kararların daha kesin olmasını sağlar. Algoritmanın başarısını ise çalıştığı en iyi duruma göre ölçmek yanıltıcı olabilir çünkü her zaman en iyi durumla karşılaşılmaz.
Algoritma analizinde kullanılan en önemli iki ölçü hafıza ve zaman kavramlarıdır. Yani bir algoritmanın ne kadar hızlı çalıştığı ve çalışırken ne kadar hafıza ihtiyacı olduğu, bu algoritmanın performansını belirleyen iki farklı boyuttur.
En iyi algoritma en hızlı ve en az hafıza ihtiyacı ile çalışan algoritmadır. İşte en kötü durum analizi olayın bu iki boyutu için de kullanılabilir. Yani en kötü durumdaki hafıza ihtiyacı ve en kötü durumdaki hızı şeklinde algoritma analiz edilebilir.
Limit teorisindeki master teoremde büyük O ile gösterilen (big-oh) değer de bu en kötü durumu analiz etmektedir. Bu yüzden en kötü durum analizine, büyük O gösterimi (Big-O notation) veya algoritmanın sonsuza giderken nasıl değiştiğini anlatmak amacıyla büyüme oranı (growth rate) isimleri verilmektedir.
Örnek
Bir çok terimli fonksiyonun (polynomial function) big-o değerini hesaplamaya çalışalım. Örnek olarak fonksiyonumuz aşağıdaki şekilde olsun:
f(x) = 3x4+2x2+5
Fonksiyonun üst asimtotik sınırı (asymptotic upper bound), her zaman için fonksiyona eşit veya daha yüksek değer veren ikinci bir fonksiyondur.
Bu durumda, yukarıdaki f(x) fonksiyonu için O(x4) denilmesinin anlamlı, herhangi bir sayı ile x4 değerinin çarpımının, f(x) fonksiyonuna eşit veya daha yüksek üreteceğidir. Bu durum aşağıdaki şekilde gösterilebilir:
f(x) ≤ cx4
Gerçekten de bu değer denenirse, c=4 için aşağıdaki çizim elde edilebilir:
Yukarıdaki mavi renkte görülen fonksiyon 4x4 ve kırmızı renkte görülen fonksiyon da f(x) fonksiyonudur. Görüldüğü üzre x>1 için 4x4 fonksiyonu, f(x) fonksiyonundan büyüktür. Dolayısıyla tanımımıza x>1 koşulu eklenebilir.
Kısaca f(x) = O (g(x))
tanımı, f(x) ≤ c.g(x)
şeklinde yorumlanabilir. Buradaki c değeri herhangi sabit bir sayıdır ve sonuçta elde edilen değer eşit veya daha büyüktür.
Büyük-O (Big-O) gösterimi ile kardeş olan bir gösterim de küçük-o (small-o) gösterimidir. Bu iki gösterim arasındaki temel fark küçük-o gösteriminde asimptotik üst sınır (asymptotic upper bound) fonksiyonunun tamamıncan büyük olmasıdır. Yani büyük-O gösterimindeki eşitlik durumu yoktur.
f(x) = og(x) için
f(x) < c g(x) şartı sağlanmalıdır.
Dolayısıyla f(x) = O (f(x)) tanımı doğru olurken f(x)=o(f(x)) tanımı hatalıdır.
Bazı örnekler aşağıda verilmiştir:
√x=o(x)
Yukarıda görüldüğü üzere x>1 için √x=o(x) doğrudur. Ancak x≥1 durumunda √x=O(x) yazılmalıdır.
log(x) = o(x)
Yukarıdaki şekillerde krımızı ile gösterilen f(x) fonksiyonlarının small-o fonksiyonları mavi renk ile çizilmiştir.
H(n)= 1+ 1/2 + ……+ 1/n ifadesinin algoritma karmaşıklığı nedir? Bu soruda bana yardımcı olabilir misiniz?
bottom up approach kullanalim ve base line ile başlayalım:
H(1)=1
H(2) = 1 + 1/2
H(2) = H(1) + 1/2
H(3) = 1 + 1/2 +1/3
H(3) = H(2) + 1/3
demek ki H(n) = H(n-1) + 1/n
o halde O(n) denilebilir.
Benzer şekilde top down approach kullanırsak
H(n-1) = 1+ … + 1/(n-1) şeklinde yazılabilir
H(n) = H(n-1) + 1/n olacaktır.
Bu arada, karmaşıklık konusunun yanında ufak bir dipnot olarak bu sayı gamma sabiti denilen değerdir
gamma = 0.57721566490153286061…
Hocam çok teşekürederim…
Hocam bide şuna bakın kendimce yaptığım H(n)<= 1+1/2+…+1/n
H(n)<= 1+1+1+1……..+1
n tane 1 var.
o zaman H(n)<= n*1 ise O(n) olur. bir böyle birşey yaptım bide
1/n parantezine alırsak
H(n)= 1/n[n+ n/2+n/3+…+1]
H(n)=1/n[n+n+n+n+……+n]
H(n)=1/n[n^2]
sonuç 1/n(log n^2)
bide böyle bir sonuca ulaştım. sonuca bakarsak birinci yaptığım dğru herhalde sizde aynı sonucu söyledinizde… ikinci bulduğum gibi bir yolla yapılamaz mıki….
son yaptığım metodta 1/2O(log n^2) olacak…
gene yanlış yazdım 🙂 1/nO(log n^2)