Algoritma Nedir ?
Algoritma Analizini detaylı bir şekilde incelemeden önce Algoritma hakkında bilgi sahibi olmamız gerekiyor.Kısaca açıklayacak olursak; algoritma, bir problemi çözmek için kesin ve açık bir şekilde belirtilmiş bir dizi talimat olarak tanımlanabilir.

Örneğin n elemanlı bir A dizisindeki girdi değeri bulan ve bulunduğu konumu geri döndüren (değer bulunamıyorsa -1 döndüren) algoritma şu şekildedir:

Biz algoritmanın etkinliğini tam olarak hesaplamak istiyoruz. Bu noktada öncelikle o algoritmadaki temel işlemi bulmalıyız. Yukarıda verdiğimiz arama algoritmasındaki temel işleme bir bakalım. Bu algoritma için temel işlem karşılaştırma işlemi. ( if A[i] = girdi] ) Temel işlemi bulduktan sonra bizi sonuca götürecek konu bu temel işlemin ne kadar tekrarlandığı.

ALGORİTMA ANALİZİ NEDİR, NE İŞE YARAR ?

Algoritma Analizi bilgisayar programlarının performans ve kaynak kullanımı üzerine teorik çalışmadır.Algoritma analizinde öncelikle ve özellikle
performans üzerinde durulur. Bilgisayar Programlarında işlerin nasıl daha hızlı gerçekleştirilebileceği ele alınır. Algoritma analizinde öncelikle ve özellikle performans üzerinde durulur. Bilgisayar Programlarında işlerin nasıl daha hızlı gerçekleştirilebileceği ele alınır.

Algoritma Karmaşıklığı ve Büyük O Gösterimi (Big O Notation) 

Yazdığımız bir algoritmanın doğru çalıştığından emin olmakla birlikte bu algoritmayı, daha önce yazılmış ve aynı sonucu veren başka algoritmalarla karşılaştırmak isteyebilirsiniz. Burada teknik olarak değerlendirilecek başlıca iki başlık söz konusudur. Birincisi algoritmaların bellek kullanım miktarı, ikincisi ise algoritmaların hesaplama yapmak için harcadığı süredir. Mesela yazdığınız bir algoritma aynı işi yapan diğer bir algoritmadan daha hızlı çalışmasına rağmen çoğu bilgisayar için bellek aşımı gerçekleştiriyorsa bu pek uygun olmayacaktır. 

Elbette diğer algoritmalarla karşılaştırma yapmak yerine, yazdığınız bir algoritmanın tek başına analizini yapmak da isteyebilirsiniz. Bunun için yazdığınız algoritmaları ve varsa karşılaştıracağınız algoritmaları tek tek çalıştırıp hız ve bellek testi yapabilirsiniz. Ama bu tahmin edebileceğiniz gibi hem zaman açısından sıkıntı yaratır hem de elde edeceğiniz veriler donanımsal ve sistemsel değişikliklerden dolayı bilimsel olmaz.(Bu gibi işlemleri performans testi olarak da düşünebiliriz) . Bu durumda matematiksel olarak ifade edebileceğimiz, donanımsal ve sistemsel bağımlılığı olmayan bir yönteme ihtiyacımız olacaktır. Bu yöntemle algoritmamıza girdi olarak verilen verilerin miktarına bağlı olarak sonuçlar üretiriz. İşte elde edilen bu sonuçlar ilgili algoritmanın karmaşıklığı olarak tanımlanır. Bir algoritmanın karmaşıklığı performansını etkiler ama karmaşıklık ile performans farklı kavramlardır görüldüğü gibi. Karmaşıklık hesabı yapacağımız asimptotik notasyonlardan en çok kullanılanını açıklamaya çalışayım.

ÇALIŞMA ZAMANI ANALİZİ

Bir algoritmanın performansı iç ve dış faktörlere bağlıdır. …

 Algoritma 1  T1(N)=1000N … 

Algoritma 2  T2(N)=N2

N değerinin 1000’den küçük olduğu durumlarda iki algoritma arasındaki çalışma zamanı ihmal edilebilir büyüklüktedir.

Büyük O Notasyonu (Big O Notation) 

O notasyonu ilk olarak 1894 yılında Alman matematikçi Bachmann tarafından kullanılmış ve Landau tarafından da yaygınlaştırılmıştır. Bu yüzden adına Landau notasyonu veya Bachmann–Landau notasyonu da denmektedir. Algoritmanın en kötü durum analizini yapmak için kullanılan notasyondur. Matematiksel olarak şöyle tanımlanır: f(x) ve g(x) reel sayılarda tanımlı iki fonksiyon olmak üzere, x > k olacak şekilde bir k vardır öyle ki, |f(x)| < C*|g(x)| dir ve      f(x)£ O(g(x)) şeklinde gösterilir. Burada C ve k sabit sayılardır ve x’ten bağımsızdırlar. 

Bilgisayar bilimlerinde kullanılan karmaşıklık sınıfları 5 tanedir.

1. Küçük-o (small-o)
2. Büyük-O (big-o, veya big-oh diye de geçer)
3. Teta (Theta Θ, sadece büyük tetadan bahsedebiliz)
4. Büyük omega (big-Ω )
5. Küçük omega(small-ω )

Arama işleminin n adet sayı üzerinde yapıldığını söylersek, aşağıdaki 3 durumu incelememiz gerekir:

1. En kötü ihtimalle kaç adımda bulunur? (worst case)
2. En iyi ihtimalle kaç adımda bulunur? (best case)
3. Ortalama kaç adımda bulunur? (average case)

Bu ihtimal analizini doğrusal arama algoritmamıza uyguladığımızda, karşılaşabileceğimiz en kötü durum aranan sayının dizinin en sonunda bulunması veya dizide hiç bulunmamasıdır. Bu durumda dizideki bütün elemanlara bakılması gerekecektir. Dolayısıyla en kötü durumda karmaşıklığımız n sayı için n olacaktır.

En iyi ihtimal ise, ilk bakılan sayının, aranan sayı olmasıdır. Bu durumda tek bir bakma işlemi yeterlidir. Bu durumdaki karmaşıklığımız ise 1 olacaktır.

Ortalama durum ise bu algoritmanın çok sefer çalışması sonucunda istatistiksel olarak ortalama kaç elemana bakılacağıdır. Bu dizide bulunan sayıların hepsinin aranma oranlarının eşit olduğunu kabul edersek, ortalama durum n/2 olur.

İşte yukarıdaki bu durum analizleri, bizim karmaşıklık sınıflarımızı veren analizlerdir.

O – En kötü durum analizi

Θ – Ortalama durum analizi

Ω- En iyi durum analizi

İşletim Zamanı  

Worst-Case Running Time : Bu işletim süresi, her girdi boyutundaki herhangi bir girdi için en uzun işletim süresini tanımlar. Örnek olarak bir programın en kötü ihtimalle ne kadar süreceğinin tahmin edilmesi istenen bir durumdur. n elemanlı bir listede sıralı arama en kötü ihtimalle (aranan bulunamazsa) n karşılaştırma gerektirecektir. Yani worst-case running time (işletim zamanı) T(n) = n’dir. Tüm problemlerde sadece en kötü girdi dikkate alındığı için worst-case running time değerini hesaplamak göreceli olarak kolaydır.

 Average-Case Running Time : Bu işletim süresi, her girdi boyutundaki tüm girdilerin ortalamasıdır. n elemanın her birinin aranma olasılığının eşit olduğu varsayıldığında ve liste dışından bir eleman aranmayacağı varsayıldığında ortalama işletim süresi (n+1)/2’dir. İkinci varsayım kaldırıldığında ortalama işletim süresi [(n+1)/2,n] aralığındadır (aranan elemanların listede olma eğilimine bağlı olarak). Ortalama durum analizi basit varsayımlar yapıldığında bile zordur ve varsayımlar da gerçek performansın iyi tahminlenememesine neden olabilir.

Örnek olarak : f(n) = n4 + 100n2 + 10n + 50 = O(n4) fonksiyonunda n'in derecesi n4'tür yani n'in büyük değerleri için fonksiyonu en fazla n4 etkiler. Peki daha düşük dereceli deyimlere ne olmaktadır? n'in çok büyük değerleri için n4, 100n2'den, 10n'den ve 50'den çok büyük olacağından daha düşük dereceli terimler dikkate alınmayabilir. Bu diğer terimlerin, işlem süresini etkilemedikleri anlamına gelmez; bu yaklaşım yapıldığında n'in çok büyük değerlerinde önem taşımadıkları anlamına gelir. n, problemin boyutudur. Yığıt, liste, kuyruk, ağaç gibi veri yapılarında eleman sayılarıdır. n elemanlı bir dizi gibi ...

O(1) : Sabit zaman

 Örnek : n elemanlı bir dizinin i. elemanına bir değer atanması O(1)’dir. Çünkü bir elemana indisinden doğrudan erişilmektedir.

O(n) : Doğrusal zaman 

Örnek : n elemanlı bir dizinin tüm elemanlarının ekrana yazdırılması O(n)’dir. Örnek : sıralı olmayan bir dizideki (listedeki) elemanlardan birinin aranması O(n)’dir (en kötü durumda da, ortalama durumda da)

O(log2n) : O(1)’den fazla O(n)’den azdır. 

Örnek : Sıralı bir listenin elemanları içinde ikili arama (binary search) uygulanarak belirli bir değerin aranması O(log2n)’dir. 

O(n2) : İkinci dereceli zaman Örnek : Basit sıralama algoritmalarının birçoğu (selection sort gibi) O(n2)’dir.

O(n log2n) : Bazı hızlı sıralama algoritmaları O(n log2n)’dir.

O(n3) : Kübik zaman Örnek : Üç boyutlu bir tamsayı tablosundaki her elemanın değerini artıran algoritma.

O(2n) : Üstel zaman, çok büyük değerlere ulaşır.


 

BÜYÜK O (BIG O) NASIL HESAPLANIR?

Bir program kodunun zaman karmaşıklığını hesaplamak için 5 Kural;

1 Döngüler

2 İç içe Döngüler

3 Ardışık deyimler

4 If-then-else deyimleri

5 Logaritmik karmaşıklık

1 Döngüler

Bir döngünün çalışma zamanı en çok döngü içindeki deyimlerin çalışma zamanının iterasyon sayısıyla çarpılması kadardır.

Toplam zaman = sabit c * n = cn = O(N)

2 İç içe Döngüler

İçteki analiz yapılır. Toplam zaman bütün döngülerin çalışma sayılarının çarpımına eşittir

Toplam zaman = c * n * n * = cn2 = O(N2)

3 Ardışık deyimler

Her deyimin zamanı birbirini etkiler

toplam zaman = c0 + c1n + c2n2 = O(N2)

4 If-then-else deyimleri

En kötü çalışma zamanı:test zamanına then veya else kısmındaki çalışma zamanının hangisi büyükse o kısım eklenir.

Toplam zaman = c0 + c1 + (c2 + c3) * n = O(N)

5 Logaritmik karmaşıklık

Toplam zaman = c0 + c1 + (c2 + c3) * n = O(N)

Problemin büyüklüğünü belli oranda(genelde ½) azaltmak için sabit bir zaman harcanıyorsa bu algoritma O(log N)’dir.

Örnek algoritma (binary search):

N sayfalı bir sözlükten bir sözcük arama

Sözlüğün orta kısmına bakılır

Sözcük ortaya göre sağda mı solda mı kaldığı bulunur?

Bu işlem sağ veya solda sözcük bulunana kadar tekrarlanır

ÖRNEKLER

f1(n) = 10 n + 25 n2

f2(n) = 20 n log n + 5 n

f3(n) = 12 n log n + 0.05 n2

f4(n) = n1/2 + 3 n log n

Dizi arama

    Ø  ›Worst case = O(n) Average case = O(n)

Quick sort

    Ø  ›Worst case = O(n2) Average case = O(n log n)

Merge Sort, Heap Sort

    Ø  Worst case = O(n log n) Average case = O(n log n)

Bubble sort

    Ø  ›Worst case = O(n2) Average case = O(n2)

Binary Search Tree: Bir elaman için arama

    Ø  ›Worst case = O(log n) Average case = O(log n)

İkili Arama (Binary Search)

Ø  İkili aramada dizi sıralanmış olduğundan, dizinin ortasında bulunan sayı ile aranan sayıyı karşılaştırarak arama boyutunu yarıya düşürülür ve bu şekilde devam edilir.

Ø  Bu algoritmanın temel mantığı aranacak elemanı dizinin ortasındaki eleman ile karşılaştırıp, aranacak eleman eğer bu elemana eşitse, amaca ulaşılmıştır. Eğer eşit değilse, bu durumda aranacak eleman dizinin hangi parçası içinde olabileceği kararı verilir. Bu sayede arama boyutu yarıya düşürülür ve bu şekilde devam edilir.

Ø  Yazdığım ikili arama örneği : https://github.com/Huseyincobanoglu/BinarySearch-Karmas-kl-k-hesaplama

Bubble Sort ( Kabarcık sıralaması ) Algoritması.

Ø  Genel Özellikleri :Bubble Sort algoritması en eski sıralama algoritmalarından biridir.Yapısı ve kodlanması itibarı ile basit olup en büyük dezavantajı yavaş olmasıdır. O(n^2) karmaşıklığındadır.

Ø  Yazdığım bublesort örneği : https://github.com/Huseyincobanoglu/bubbleSort

Insertion Sort Algoritması

  Ø  Insertion Sort, bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öge öge oluşturan bir sıralama algoritmasıdır. 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. Genelllikle günlük hayatımızda farketmeden kullandığımız bir çözüm yöntemidir. Küçük boyutlu dizileri sıralamada hızlı olsa da çok sayıda veriyi sıralarken Insertion Sort diğer sıralama yöntemlerine göre çok yavaş kalmaktadır.

  Ø  Yazdığım insertion sort örneği : https://github.com/Huseyincobanoglu/insertion-sort

Hızlı Sıralama (Quick Sort) Algoritması

Ø  Quick sort algoritması türkçe adıyla hızlı sıralama algoritması, günümüzde hala sıklıkla kullanılan bir algoritmadır. Sıralanması istenen dizi, dizi içerisinden belirlenen bir nokta (pivot noktası) yardımıyla iki alt diziye ayrılır. Pivot noktasından küçük olan elemanlar soldaki birinci alt diziye, büyük olan elemanlar ise sağdaki ikinci alt diziye taşınır. Daha sonra, yine aynı algoritma rekürsif olarak çağrılarak bu alt dizilerin sıralanması istenir. Bu işlem diziler parçalanamayacak duruma gelene kadar sürdürülür

Ø  Yazdığım Quick Sort örneği : https://github.com/Huseyincobanoglu/quickSort

Hash Tablosu

  Ø  Hash tablosu, veriye bir anahtar (key) yardımı ile erişilen basit bir dizi üzerine bina edilmiştir.Anahtar kullanılarak bir indeks üretilir ve bu indeks ile dizideki istenen veriye ulaşılır.Anahtar tekildir yani bir başka kayıtta aynı anahtar olamaz. Ancak veri aynı olabilir. Bir sınıftaki öğrenciler buna çok iyi bir örnektir. Her öğrencinin sadece kendine ait bir numarası vardır. Ancak aynı isme sahip iki öğrenci olması muhtemeldir. Burada öğrenci numarası anahtardır; öğrenci ismi ise, bu anahtara ait veridir.

  Ø  Yazdığım Hash Tablosu örneği :https://github.com/Huseyincobanoglu/HashTable

Dinamik Dizi

Ø  Dinamik dizilerdeki ekleme ve silme işlemlerinin temel mantığı dizilerdeki gibidir. Aradaki farklılık sabit boyutlu bir dizinin kapasitesi dolduğunda yeni veri ekleme işleminin hata ile sonuçlanması, dinamik dizilerde ise aynı işlemin boyut değişimi sayesinde başarılı olmasıdır.En basit dinamik dizi yapısında arka planda çalışan iki dizi kullanılmaktadır. Bunlardan ilki veriyi tutmaktadır, ikincisi ise tampon bölge olarak görev yapmaktadır. Birinci bölge oluşturulduğunda dizi yeni oluşturulan daha büyük boyutlu bir diziye kopyalanarak ilk dizi silinmektedir. Sınır durumdaki ekleme işlemi hakkında bir irdeleme yapılmalı ve dinamik dizinin ne zaman genişletilmesi gerektiğine çok iyi karar verilmelidir. Çünkü genişletme, eklemeye göre daha masraflı bir işlemdir. Birkaç elemandan oluşan dizilerde bu masraf göz ardı edilebilecek kadar düşük bir maliyette olsa da dizinin eleman sayısı arttıkça bu maliyette artmaktadır.

Ø  Yazdığım dinamik dizi örneği : https://github.com/Huseyincobanoglu/vector-kapasitesini-art-rma