The Analysis Framework

Kategori: Algorithm Design and Analysis , 31 Mayıs 2020 , JanFranco


Bu bölümde algoritmaların analizini yapacağız, verimlilikleri ölçeceğiz. Verimliliği iki ana kısımda inceleyebiliriz: Time efficiency ve space efficiency. Zaman verimliliği aynı zamanda time complexity olarak da geçer ve bir algoritmanın hızını baz alır. Yer verimliliği ise space complexity olarak geçer ve algoritmanın input ve outputlar ile birlikte bellekte kapladığı alanı baz alır.

Verimliliği ölçerken bu algoritma 3 saniyede çalıştı şeklinde bir söylemde bulunamayız. Bir bilgisayarda 3 saniye iken bir bilgisayarda 0.1 saniye bir bilgisayarda 5 saniye sürebilir. Çalıştırıldığı device, compiler vs. fark yaratabilir.

Verimlilik için ilk olarak giriş büyüklüğü hesaplanmalıdır. Örneğin 0'dan n'e kadar olan bir listenin giriş büyüklüğü n'dir. Girilen sayının faktöriyelini alan algoritmanın giriş büyüklüğü sayı kadardır (3!, 3). Bazı durumlar için boyutu iki şekilde ele alabiliriz. Örneğin n x n boyutlu bir matriste girdi büyüklüğü n de olabilir N (n x n, 3 x 3 = 9) de olabilir. Girdi büyüklüğünü belirledikten sonra, temel operasyonumuzu bulmalıyız. Temel operasyon en çok zaman alan operasyondur. Örneğin faktöriyel alıyorsak, temel operasyon çarpmadır. Dizide arama yapıyorsak temel operasyon karşılaştırmadır. Temel operasyonu da bulduktan sonra bu operasyonun kaç kez çalıştırılacağını bulmalıyız. Daha sonra aşağıdaki formülü uygulayabiliriz:

T(n) ~~ temel operasyonun çalışma süresi * temel operasyonun kaç kez yapılacağı

Bu formülü çalışma süresi bilinmediği durumlarda oranlayarak kullanabiliriz. Örneğin bir algoritmadaki temel operasyonun kaç kez yapılacağı aşağıdaki formül ile belirlendi:

C(n) = 1/2 * n * (n - 1) = 1/2 * n^2 - 1/2 * n ~~ 1/2 * n^2

Burada girdi boyutumuz iki katına çıkarsa:

T(2n)/T(n) ~~ Cop * C(2n) / Cop * C(n) ~~ 1/2 * (2n) ^ 2 = 4

Burada 4 değeri, girdi boyutunu iki katına çıkardığımızda algoritmanın 4 kat daha yavaş çalışacağını söylüyor. Dikkat ettiyseniz Cop yani temel operasyonun çalışma süresini bilmeden bunu bulabildik.

Algoritmaların efektifliğini ölçerken üç durumu göz önünde bulundurabiliriz: worst case, average case, best case. Worst case algoritmanın en yavaş çalıştığı an, best case ise en iyi çalıştığı andır. Örneğin bir dizide bir eleman aradığımızı düşünelim. Eğer algoritmamız linear bir algoritma ise Worst case yani en kötü durum objenin dizide olmaması durumudur. Çünkü dizinin başından sona kadar bu objeyi arayacağız. Best case durumu ise en iyi algortma durumudur. Bu duruma aynı örnek üzerinden devame edersek, aradığımız objenin dizinin 0. indisinde olduğunu göyoruz. İşte bu algoritmanın en hızlı çalıştığı durumdur. Ortalama durumda yani average case'leri daha farklı bir yolla hesaplarız. Tüm değerlerin bir olasılık değeri vardır. Bir dizide bir objeyi arıyorsak, tüm elemanların gelme olasılığı düşüktür Aşağıda bir average case durumunun nasıl incelendiğini görüyoruz:

Cavg(N) = [1 * P / n + 2 * p / n...] + n * (1 - p) =
P / n * [1 + 2 + ... + 4 + i] + n * (1 - p) =
P/n * n(n + 1)


Sonraki Yazı: Asymptotic Notations
Yorumlar

Henüz bir yorum bulunmuyor.