Algoritma Analizi

ensr <ensar.hamzacebi@bil.omu.edu.tr>

http://ensr.github.io/

Nisan 2014

Presenter Notes

T(n)

  • Problemin boyutu

  • Algoritmada gerçekleştirilen işlem sayısı

    def sumOfN(n):
    sum = 0
    for i in range(1, n+1):
        sum = sum + 1
    return sum

Presenter Notes

Arama

Ardışıl (Sequential) Arama

  • Listede sırayla dolaş

  • Aranılan eleman ile karşılaştır

  • Eşleşme sağlandığında çık

Presenter Notes

Arama

İkil Arama

  • Listeyi küçükten büyüğe sırala

  • Listenin ortasındaki elemana git karşılaştır

  • Aranan eleman daha büyükse * Sağdaki yarım listenin ortasına git

  • Aranan eleman daha küçükse * Soldaki yarım listenin ortasına git

  • Eşleşma sağlanıncaya kadar devam et

Presenter Notes

Arama

Maliyet

  • n (liste boyu) küçükse bir kere sırala ikil ara

  • n büyükse sıralama maliyetli

  • Ardışıl arama yap

Presenter Notes

Hash (Çırpı)

  • Elemanları listeye çakışma olmayacak şekilde yerleştir

  • Daha sonra kolayca erişebileceğimiz şekilde

  • Bellek kullanımını minimuma düşür

  • Her eleman için bir slot belirle ve o slota kaydet

  • Yük oranı = (yerleştirilmiş eleman sayısı) / (liste boyutu)

  • Yük oranını olabildiğince 1’e yaklaştır

Presenter Notes

Hash

Mükemmel Çırpı

  • Çakışmanın sıfır olduğu hash’dir

  • Liste boyutu eleman sayısı kadardır

  • Yük oranı 1’dir

Presenter Notes

Çakışma (Collusion) Çözümleme

  • Çakışma: Aynı slot’a iki elemanın talip olması

  • Açık adresleme

  • Zincirleme

Presenter Notes

Çakışma

Açık Adresleme

  • Çakışma varsa liste içinde sırayla ilerle

  • İlk boş slot’a yerleştir

Presenter Notes

Çakışma

Zincirleme

  • Çakışma varsa o slot’ta liste oluştur

  • Elemanı o listeye ekle

Presenter Notes

Sıralama

  • Liste elemanlarını sıralama algoritmaları

  • Baloncuk (Bubble) Sıralama

  • Seçmali (Selection) Sıralama

  • Araya Girmeli (Insertion) Sıralama

Presenter Notes

Sıralama

Baloncuk (Bubble) Sıralama

  • Listede dolaş

  • Komşu elemanları karşılaştır

  • Gerekirse yer değiştir

  • Her eleman doğru yerine gelinceye kadar devam et

Presenter Notes

Sıralama

Seçmeli (Selection) Sıralama

  • Listedeki en büyük elemanı bul

  • Listenin en sonuna koy

  • Sonraki en büyük elemanı bul

  • En sonun bir yanına koy

  • Sıralama tamamlanıncaya kadar devam et

Presenter Notes

Sıralama

Araya Girmeli (Insertion) Sıralama

  • Liste içinde dolaş

  • Seçilen her elemanı öncekilerle sırayla karşılaştır

  • Doğru araya yerleştir

  • Listede ilerlendikçe geride sıralı bir liste oluşmaya başlar

Presenter Notes