Herkese merhaba, bu yazımda algoritma analizinin ne demek olduğunu, neden gerekli olduğunu ve nasıl yapıldığını okulda bir dönem boyunca almış olduğum dersin katkılarıyla aktarmaya çalışacağım.
Öncelikle algoritma ve algoritma analizinin ne olduğundan bahsedelim. Algoritma, belirli bir problemi çözmek veya belirli bir amaca ulaşmak için tasarlanan yoldur. Tabi bu çözüme ulaşmak için tasarladığımız yolda yapılacak işlerin adım adım adım ortaya konulması ve bu adımların sıralaması önemli. Bir problem için birden fazla algoritma verilmişse bu algoritmalardan en iyisi seçilmelidir. Algoritma analizi burada devreye girer ve farklı çözüm yöntemlerinin verimliliğini analiz eder. İyi algoritmayı belirlemek için uygulanan testler ve yapılan işlemler Algoritma analizinin konusudur. Algoritma analizi algoritmayı gerçekte uygulamadan algoritmanın çalıştırılabilmesi için gerekli kaynakların araştırılması demektir. Burada bahsettiğim gerekli kaynaklar temelde iki önemli kaynak olan bellek ve zamandır. Bellek, programın işletildiği sürece gerekli olan yer miktarıdır. Zaman ise programın işletim süresidir. Bir bilgisayar programı için benzer amaçlı algoritmaları kıyaslayacak olursak ne kadar fazla yer kaplıyor ve ne kadar yavaş çalışıyorsa o kadar kötüdür diyebiliriz. Algoritmayı tercih ederken elimizdeki zaman ve yer kısıtlarına göre en verimli olanı tercih etmeliyiz.
Algoritmaların analizinin nasıl yapıldığından bahsedecek olursak, algoritmaların etkinliğini değerlendirmek için belirli bir çözümde anlamlı olan işlemlerin kaç adet olduğu sayılır. Daha sonra büyüme fonksiyonları kullanılarak algoritmaların verimliliği ifade edilir.
Yazının devamında algoritmanın karmaşıklığının nasıl bulunduğuna dair bol bol örnek olacak şimdilik karmaşıklığın gösterimi için gerekli olan notasyonlardan bahsedelim.(asymptotic notation)
O(f(x)) Big O : Üst sınır. Algoritmanın en kötü durum analizini yapmak için kullanılan notasyondur.
Big O asimptotik notasyonlardan en çok kullanılanıdır.
Ω(f(x)) Omega : Alt sınır. Programın çalışması için bir alt sınır belirler. Yani programın en iyi durumda nasıl çalışacağını gösterir.
Θ(f(x)) Teta : Programın alt sınırı ile üst sınırının aynı olması durumunda kullanılır . Yani O(n)=Ω(n) ise Θ(n)'dir diyebiliriz.
o(f(x)) Küçük o : Genelde ağaç yapılarındaki gösterimler için kullanılır.
Algoritmanın büyüme oranlarına bakılarak verimliliklerini karşılaşrıtabilir. n sayısı için yeterince değerleri için daha küçük büyüme oranları her zaman daha hızlıdır.
Yukarıda tablodaki büyüme oranlarının big O notasyonu için zamana göre değişim grafiği aşağıdaki şekildeki gösterebiliriz.
Başlangıç olarak basit bir örnek olması için N tane sayının küplerinin toplamnı bulan fonksiyonun karmaşıklığını bularak analizin nasıl yapıldığını görelim.
Örnek :
Yukarıdaki kodda atama işlemi karşılaştırma işlemi şeklinde ilk iki kodda belirttim ancak bunları hesaplamaya katmıyoruz. Sadece kaç kere tekrar ettiklerine bakıyoruz desek yanlış olmaz sanırım. Zaten sonuç olarak 3n+6 bulmama rağmen karmaşıklığın O(n) olduğunu görebiliriz. Bir işlemi 1 kez yapmış yada 10 kez yapmış olması bizim için kritik nokta değil. Yukarıdaki algoritmanın çalışma zamanı n ile doğru orantılıdır.
İçiçe döngülerde karmaşıklık hesabı içten dışa doğru olur. Grubun içindeki deyimin toplam çalışma zamanı, deyimlerin çalışma sürelerinin bütün döngülerin boyutların çarpımı kadardır. if else yapısında test zamanında hangi kısımdaki çalışma zamanı büyükse o kısım alınır.
Arama algoritmalarından doğrusal ve ikili arama algoritmalarının karmaşıklıklarını inceleyelim.
-Doğrusal (Lineer) Arama
Doğrusal arama bir dizinin içinde bir verinin olup olmadığını anlamak için kullanılan basit bir algoritma. Dizinin başından sonuna kadar bütün elemanları gezerek aradığımız değerle bütün elemanları tek tek karşılaştırır. Aradığımız değer dizide varsa bulunduğu yerin indisini, yoksa -1 verir. Bu algoritmada n sayılı bir dizi içinde arama yaptığımızı ve aradığımız değerin dizinin son elemanında olduğunu düşünürsek aradığımız değere eşit mi diye bi karşılaştırmayı n kez yapmış oluruz. Bu durumda karmaşıklık worst case için O(n) olur. aradığımız eleman dizinin ilk elemanıysa bu durumda sadece tek bir elemanla karşılaştırmış oluruz ve best case Ω(1) olur.
Doğrusal arama için C koduna buradan ulaşablirsiniz.
- İkili (Binary) Arama
İkili arama aranacak veri yapısını her adımda ikiye bölerek arama yapar. Bu algoritmanın dizi üzerinde başarılı çalışması için dizinin sıralı olması gerekir. Algoritmanın çalışma mantığı; aranan uzayın tam orta noktasına bak aradığımız değer ordaysa işlemi bitir değilse aradığımız değer baktığımız yerdeki değerden küçükse aramayı küçük elemanların olduğu uzayda devam ettir. Daha büyükse büyük elemanların olduğu uzayda aramaya devam et. Baktığımız aralık 1 yada daha küçükse bulunamadığını bildir ve sonlandır şeklindedir.
İkili arama algoritmasında aradığımız değer ortadaki değer ise tek karşılaştırmayla aradığımızı bulacağımız için bu en iyi durumdur. Yani best case Ω(1) olur. En kötü durumda ise aradığımız uzayı 2 ye bölerek ilerlediğimiz için k kez böldüğümüzü düşünürsek;
2n
= k buradan k=log2n yani worst case : O(logn) olur.
İkili arama algoritması için zaman karmaşıklığını bulan Python koduna buradan ulaşablirsiniz.
ikili arama algoritması için karşılaştırma sayısını bulan C koduna buradan ulaşabilirsiniz.
Algoritma analizi karmaşıklık hesaplamalarımıza fibonacci fonksiyonları ile devam edelim.
-Fibonacci Serisini Bulma
Fibonacci dizisi her sayının kendinden öncekiyle toplanması sonucu oluşan bir sayı dizisidir. Burada fibonacci dizisini bulmanın 3 farklı gerçekleştiriminin karmaşıklıklarını inceleyeceğiz. Öncelikle döngülerle bulunmasından bahsedecek olursak burada tek bir for içerisinde işlemler gerçekleştirilir. Bu fonksiyon için yazmış olduğum C koduna buradan ulaşablirsiniz. Karmaşıklık O(N)'dir.
-Recursive Fibonacci
Özyinelemeli fonksiyonun ne olduğuna kısaca değinelim. Özyinelemeli fonksiyon kendi kendisini doğrudan veya dolaylı olarak çağıran fonksiyondur. Bir problemin daha küçük benzer problemlere bölünerek çözülmesini sağlayan bi tekniktir. Örneğin 5 sayısı için yani 5. fibonacci sayısını bulmak için fib(5)= fib(4) +fib(3) şeklinde problemi böler. fib(3) ve fib(4)ün bulunmasıyla fib(5) bulunur.
Aşağıdaki şekil ile anlatmak istediğim durum daha anlaşılır hale gelebilir.
Bununla ilgili detay için C ile yazmış olduğum recursive fibonacci fonksiyonuna buradan ulaşablirsiniz. Recursive fibonacci için karmaşıklık O( 2n )
-Hafızaya alma tekniği ile recursive fibonacci
Yukarıdaki şekilde F(6) yı hesaplamak için f(4)'ü, f(3)'ü, f(2)'yi tekrar tekrar hesaplar. Hafızaya alma tekniği ile bir dizi oluşturup içindeki değerleri başlangıçta -1 yaparak bir kez hesaplandığında hesaplanan değeri dizide güncelleyerek o değer için fonksiyonun tekrar çağrılmasını engellemiş olur. 0'dan N'e kadar olan tüm sayılar için fib fonksiyonu 1 kez çağırıp değerini hesaplayıp dizide tutarak karmaşıklığı O(N)'e indirgemiş oluruz.
Hafızaya alma tekniği ile recursive fibonacci için C++ koduna buradan ulaşabilirsiniz.
Karmaşıklık hesaplamalırna sıralama algoritmaları ile devam edelim.
-Bubble Sort Algoritması (Kabarcık Sıralama Algoritması)
Bubble sort, sıralama algoritmalarının içinde en kolay olan ama büyük dizilerde çok yavaş kalan bir sıralama yöntemidir. Bu algoritmanın çalışma mantığı verilen dizinin öğelerinin veriliş sırasıyla yatay bir şekilde dizildiğini varsayalım.İlk eleman ikinci elemanla karşılaştırılır büyükse sağa geçer üçüncüelemanla karşılaştırlır büyükse sağa geçer bu şekilde en büyük eleman en sağa geçmiş olur. Ve bu eleman dışındakilerin oluşturduğu alt dizi içinde aynı şey tekrarlanır. Bu çalışma mantığından tahmin edebileceğimiz üzere içiçe 2 fora ihtiyacımız var bu da karmaşıklığın O(N2) olduğunu gösterir.
Bubble sort için yazmış olduğum C koduna buradan ulaşabilirsiniz.
-Selection Sıralama Algoritması
Selection algoritmasının çalışma mantığı her adımda dizideki en küçük elemanın nerede olduğu bulunur. Bu sayı ile dizinin başındaki sayı yer değiştirilerek en küçük sayılar seçilerek başa geçirilmiş olur. Her adımda n sayı işlenmekte ve bu n kez tekrar ettiği için algoritmanın karmaşıklığı O(N2) olur.
Selection Sort için yazmış olduğum C koduna buradan ulaşabilirsiniz.
- Insertion Sort Algoritması
Insertion sort algoritması,düzensiz dizi elemanlarını tek tek ele alarak her birini dizinin sıralanmış kısmındaki uygun yerine yerleştirme esasına dayanır. Çalışma mantığı algoritmanın küçükten büyüğe sıralama yaptığını düşünürsek; ilk olarak sayı dizisinin ikinci elemanını anahtar olarak seçer ve kendinden önceki tüm sayılarla kıyaslar. Kendinden önceki büyük olan her sayıyla yer değiştirir. Eğer küçükse yer değiştirme biter. Daha sonra dizinin son elemanına kadar anahtar seçimi ve yer değiştirme işlemleri devam eder. Burada dizideki eleman sayısı kadar geçiş gerekir ve en kötü ihtimalle eleman sayısı kadar kaydırma yapılır. Bu nedenle karmaşıklığı O(N2) olur.
Insertion Sort için yazmış olduğum C koduna buradan ulaşabilirsiniz.
-Quick Sort Algoritması
Quick Sort algoritması sıralanacak olan dizideki orta noktada bulunan bir sayıyı seçerek bu orta noktadaki sayıya pivot dersek diğer bütün sayıları pivottan büyük veya küçük diye sınıflayarak sıralama yapmayı hedefler. Bu algoritmanın karmaşıklığını incelersek; üzerinde çalıştığımız dizi her adımda en fazla 2'ye bölünmüştür. Sonuç dizisi olan 2'şer elemanlı dizilere logn adımda ulaşılır. Daha sonra her n eleman için sıralama yapıldığı ve her n eleman üzerinden geçildiği için bu sayı çarpan olarak gelir ve karmaşıklık O(nlogn) olur.
Quick sort için Python koduna buradan ulaşabilirsiniz.
Sıralama algoritmalarından sonra derste yapmış olduğumuz dinamik bir diziye eleman eklemenin maliyetinden biraz bahsedeyim.
-Dinamik bir dizi için insert işleminin maliyeti
Öncelikle n elemanlı bir dizimiz olduğunu varsayalım. Bu dizinin (n-1). indisine kadar eleman eklemenin maliyeti O(1). İndis değeri n ve n den büyük olduğunda ise maliyet değişir. Çünkü n ve n den sonra dizi için ayrılan yeri geçtiği için taşıma yapması gerekir. Dizi dolduğunda başka bir yere taşıma yani yer değişiminin maliyeti O(n) olur.
Dinamik dizi için bu yer değişimiyle ilgili yazmış olduğum C++ koduna buradan ulaşabilirsiniz.
-Bağlı Liste
Bağlı liste içindeki elemanların doğrusal olarak düzenlendiği veri yapısıdır. Bu yönüyle dizilere benzer ancak elemanlara ulaşma yoluyla dizilerden ayrılır. Dizilerde dizinin içindeki elemana dizinin indeksiyle ulaşırken bağlı listede bağlı listenin içindeki elemanlara o elemanlara işaret eden işaretçiler ile ulaşırız. Bir diziden bir eleman sildiğimizde ortaya çıkan boşluğu doldurmak için sildiğimiz elemandan sonraki her eleman kaydırılır. Bağlı listeden bir eleman silinmesi gerektiğinde yapılacak tek şey ise bir işaretçinin gösterdiği yerin değiştirilmesidir. Eleman ekleme işlemi içinde yapılacak işlemler aynı. Fakat bir elemanı arama işlemi dizide ikili arama yöntemiyle O(logn) zaman da gerçekleşirken bağlı listede tüm listeyi gezmek gerekeceğinden O(n) zamanda gerçekleşir. Bağlı liste ve dizi için ekleme, silme, arama işlemleri için karmaşıklığı aşağıdaki tablodan inceleyerek karşılaştırma yapabiliriz.
- İkili Arama Ağacı
Öncelikle ağaç veri yapısını kısacık özet geçmek gerekirse; ağaç dooğrusal olmayan bir veri yapısıdır. Ağaç veri yapısında yukarıda bir kökü vardır ve kolları aşağıya doğru genişler. Ağaçta bir düğümün hiç çocuğu yoksa o düğüme yaprak denir ve kökten yaprağa ulaşmak için geçtiğimiz elemanların sayısının en fazlası bize ağacın derinliğini verir. Bir ağacın ikili ağaç olması için en önemli şart kökün sağında kökten büyük değerler solunda kökten küçük değerler olmalıdır. Ayrıca ikili ağaçlarda her düğümün en fazla iki çocuğu bulunabilir.
İkili arama ağacında ekleme işlemi yaparken eğer ağaç full tree ise maliyet O(logn) olur. Ağaç yapısı full tree değilse yani her derinlikte bir düğüm olduğunu ve ağacın liste şekline dönüştüğünü düşünürsek bu durumda maliyet O(n) olur.
- Hash Table
Hash tablosu sadece bir dizi elemandan oluşan basit bir veri yapısıdır. Her bir eleman sayı veya string olabileceği gibi herhangi bir veri yapısıda olabilir. Tablo N elemandan oluşuyorsa hash table ın büyüklüğü N'dir ve elemanlar 0 ile N-1 arasında normal bir dizideki gibi adreslenirler. Hash Table ın özelliği elemanlar ile adreslerini birbirine bağlayan birebir fonksiyon kullanmasıdır. Bu fonksiyon hash fonksiyonudur ve bu hash fonksiyonu hem elemanları iyi serpiştirmeli hemde mümkünse iki farklı elemanı aynı pozisyona adreslememelidir. Birden fazla eleman aynı pozisyona adreslenirse çakışma olacaktır. Çakışma problemi de aynı pozisyona adreslenen elemanlrı bir bağlı listede tutarak çözülebilir. İkili arama ağacın O(logn) zamanda yapılan ekleme, silme, arama işlemleri hash table ortalama O(1) zamanda yapar. Fakat ikili arama ağacında desteklenen en büyük en küçük elemanı bulma ile verileri sıralı biçimde doğrusal zamanda ekrana yazma işlemleri hash table yaısında desteklenmez.
Aşağıdaki basit örnek hash table ın çalışma mantığını anlamaya yardımcı olabilir.
Okulda bir dönem boyunca görmüş olduğum Algoritma Analizi dersinin içeriğini özetlemeye çalıştım umarım faydalı olur.
Hiç yorum yok:
Yorum Gönder