Algoritmalar ve Karmaşıklıkları
Binary Search
İkili arama algoritması sıralı dizimizi ortadan ikiye bölerek aranılan değerin bulunup bulunmadığını; eğer bulunmadı ise arananın orta elemandan büyük mü küçük mü olduğunu kontrol eder. Diyelim ki aranan orta değerden küçüktür. Bu sefer arama algoritmamız orta elemandan büyük olan kısmı tamamen yok sayarak orta elemandan küçük olan kısmıyeni diziymiş gibi kabul eder. Böylelikle dizimiz yarıya indirgenmiş olmuştur. Sonrasında tekrardan orta değerden küçük kısmı ikiye bölerek, aranılan değerin bulunup bulunmadığını kontrol eder. Yeni orta değer aranan eleman değilse, küçük mü büyük mü diye yeniden kontrol edilir. Ve bu işlem aranan değer bulununcaya yada tamamen dizi taranıncaya kadar devam eder. Bu yüzden algoritmamızın karmaşıklığı O(logN) olur.
Binary search karmaşıklık: Worst case = O(log n) Average case = O(log n)
Bubble Sort
Bubble sortun çalışma mantığı şöyledir: dizinin başından başlanarak ikişerli kıyaslama yapılarak dizinin sonuna kadar gidilir. İlgili sıralama şekline göre kıyaslanan elemanlar yer degiştirir. Hiç bir yer degiştiren eleman kalmadıgında sıralama işlemi sonlanır. Bu işlemin maliyeti O(N^2) dir.
Buble sort karmaşıklık: Worst case = O(n^2) Average case = O(n^2)
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.
Ders kapsamında yazmış olduğum quick sort kodunu algoritma analiz yazarak github hesabıma koydum aşağıdaki linkten ulaşabilirsiniz.
Selection Sort
Selection Sort, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Karmaşıklığı olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır. Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir.
Selection sort karmaşıklık:
Best case= O(n^2) Worst case = O(n^2) Average case = O(n^2)
Insertıon Sort
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.
İnsertion sort karmaşıklık:
Best case= O(n) Worst case = O(n^2) Average case = O(n^2)
Hiç yorum yok:
Yorum Gönder