Algoritma Karmaşıklığı-Analizi

ALGORİTMA

EN İYİ DURUM

EN KÖTÜ DURUM

SEÇEREK SIRALAMA O(N2) O(N2)
YERLEŞTİREREK SIRALAMA O(N) O(N2)
İYİLEŞTİRİLMİŞ KABARCIKSIRALAMA O(N) O(N2)
KABARCIK SIRALAMA O(N2) O(N2)
HIZLI SIRALAMA NlogN O(N2)
SIRAYLA ARAMA 1 O(N)
İKİLİ ARAMA 1 logN

 

EN İYİ DURUM :
Seçerek,yerleştirerek,iyilşetirilmiş kabarcık ve Kabarcık sıralama algoritmlarında sıralanacak listenin zaten sıralı olma durumudur.
Sırayla ve ikili arama algoritmalarında ise aranan verinin ilk adımda bulunma durumudur.

EN KÖTÜ DURUM
Sıralama Algoritmlarında : listenin tam ters sırada olma durumudur.
Sırayla arama algoritmasında aranan verinin sıranın en sonunda olması durumudur.İkili arama da ise sürekli 2 ye bölerek arama yapıldıgı ıcın en kotu durumda logN adımda bulur.

 

NOT: Hızlı sıralama algoritmasında listenin sıralı olması en kötü durumdur.

ÖRNEK :

A=: {1,2,3,4,5}

Yukarıdaki listeyi sıralamak için kullanacagımız tümalgoritmaların Algoritma karmaşıklıgını O(N) Gösterimi ile ifade ediniz.

CEVAP: Verilen liste zaten sıralıdır buna göre

  • Seçerek Sıralama: için en iyi durumdur yani N2
  • Yerleştirek Sıralama için en iyi durumdur yani N
  • Kabarcık Sıralama için en iyi durumdur yani N2
  • İyileştirilmiş Kabarcık sıralama için en iyi durumdur yani N
  • Hızlı sıralama için en kötü durumdur bu yüzden N2
  • SIrayla arama için en iyi durumdur yani 1
  • ikili arama da en kötü durumdur logN
  • Doğrama yöntemiyle arama (Hashing) en iyi durumdur yani 1
Eğitim kategorisine gönderildi Etiketler: , , , , , , , , , ,

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

*