23 Kasım 2014 Pazar

Algoritma- Running time ve notasyon

   Sevgili yaprak. Yaptığım hesaba göre biram bitmeden bu konuyuda aradan çıkartırım heralde. Zaten benimde sıkıntı yaşadığım bi konuydu burda tekrar üzerinden geçerim iyi olur bence amk.
   Saat gecenin 2.20si ve aşırı uykum olduğu için doğrudan konuya giriyorum amk.(Bide yarın eskişehire gidicem amk. Uyumam lazım yani )
   Neyse Running time konudanda anlayacağınız gibi programın ne kadar çalışacağı sorusunu cevaplar. Şimdilik running time için bukadar yeterli bence.
   Big O Notation dediğidimiz o notasyonu ise, Kendi yazdığımız kodların. hazır olan algoritmaların veya işlevsel operasyonların(linked list vs.) karşılaştırılmasında kullanılır ve önemli olabilecek düzeydedir.
       Big O bi çeşit gösterim türüdür, Bunun çeşitli türevleride vardır: O , θ, Ω notasyonları
Bu notasyonlar arasına çeşitli farklılıklar vardır kısaca:
                                                                      -Big O üst sınır(algoritmanının çalışacağı en kötü durum)
                                                                      -Big θ ortalama durum
                                                                      -Big Ω alt sınır(algoritmanın çalışacağı en iyi durum)
Bu türler içinde genelde bigO notasyonunu kullanacağımız için diğerlerini bu düzeyde bilmemiz yeterlidir. gelelim big O notasyonuna;
Şimdi gençler big O notasyonu dediğim gibi en kötü durum için geçerlidir yani örneğin 1,2,3,4,5,6 elemanlarının olduğu bir dizide get methodunu çalıştırırsak bu kod sike sike en kötü durumu çalıştırır çünkü 6 en son elemanldır ve dizinin içine girebileceği en fazla miktarda girecektir kapiş?
Şu running time meselesini biraz daha ayrıntılı inceleyelimde kafalarda soru işareti kalmasın amk.
Aşağıda vereceğim kodun running time durumuna bir bakalım;
     int sum(int A[],int N){
       int sum = 0;                        ----> 1 kez çalışır
        for (int i=0;i <N,i++({      -----> N  kez çalışır                  Yandaki metod görüleceği üzere
            sum += A[i];                 -----> N kez çalışır                    2N+2 kez çalışır. bu metodun
               }                                                                                   running time'ıdır.
return sum;                               ------> 1 kez çalışır.                  T(N) = 2N+2 ile gösterilir.
}
Yukarıdaki metod için ;
                                          En iyi çalışma süresi (Best case) = N 1 olursa 2*1+2= 4
                                          Ortalama çalışma süresi(average case) =  2N/2+2 = N+2
                                          En kötü çalışma süresi(Worst case) = 2N+2
Genel çalışma prensibi budur.
Aklınızın bir köşesinde bulunmasını istediğim bir diğer nokta;
             iç içe 2 döngü varsa ve ikiside N'e kadar sürüyorsa kod n2 kadar çalışır eğer üç tane döngü olursa iç içe ozaman n3 kadar çalışır. Ne bilim belki lazım olur. belirteyim dedim.

Şimdi yapraam tekrardan notasyon konusuna dönmek istiyorum. Bu arada kişisel gelişiminiz için bu videoyada bakmanıza fayda var http://www.youtube.com/watch?v=gjRc8QwsR8k

Neyse Big O notation dediğimiz en kötü durumu gösteren notasyon türünün mantığı şudur genel gösterim O(N) veya O(n2) veya O(1) vs vs.. türlerindedir ama asla O(2+N) veya O(2N) şekillerinde gösterilmez. Nedenini sormayın amk notasyon gösterim prensibi bu.
Örneğim bir kaç metoddan oluşan bir kod dizimiz var ve ;
                                                                                                1. metod 1 kere
                                                                                                2.  metod N kere
                                                                                                3. metod n2 kere
                                                                                                4. metod 2n2 kere çalışıyor.
Ozaman bu kodun notasyonu O(n2) 'dir kuvveti en büyük olanı notasyonun içine yazarız. N ile birlikte sabit sayı koymayız
Notasyonun genel mantığı budur.
Genel notasyon gösterim türleri ve hiyerarşisine gelecek olursak;
İsim                           Gösterim
Sabit ===========> O(1)
LOG LOG =======> O(loglogN)  -> Tahminsel arama
Logaritmik =======> O(LogN) -> iyi arama algoritmalarının tipik zamanı
Doğrusal =========> O(N) ->N tane veriyi girmek için gereken zaman
N LOG N ========> O(NlogN) -> Çoğu sıralama algoritması
Karesel =========> O(n2) -> veri miktarı azsa

hiyerarşiye gelicek olursak => O(n2) > O(n log n) > O(n) > O(log n) > O(1)
Şimdide güzel bir örnekle bu konuyu kapatalım (Şimdilik)
for(i = 0 ; i< n ; i++ ){
 mesaj = "Yapraam" + i; // n kere O(1)
}
// Ara sonuç:  O(n)
mesaj = "Merhaba yapraam"; // O(1)
int x = 10; // O(1)
// Ara sonuç: O(n) + 2*O(1)

for(i = 0 ; i< n ; i++ ){

 mesaj = "Merhaba"; // O(1)
 mesaj = "Yapraam" + i; // O(1)
 // n kere 2*O(1)
}
// Ara sonuç: O(n) + 2*O(1) + 2*O(n)
// Ara sonuç: 3*O(n) + 2*O(1)
// Sonuç: O(n)

Yapraklarım notasyon ve running time meselesi kabataslak bu şekildedir. İlerleyen zamanlarda daha ayrıntılı giriş yapıcam merak etmeyin.

Hiç yorum yok:

Yorum Gönder