Algoritma Karmaşıklığı

Merhaba. Bu konuda iki sıralama algoritmasından bahsedeceğim. Heap sort ve Merge sort. Bu iki algoritma zaman karmaşıklığı olarak aynı değerlere sahiptir(nlogn).Bildiğimiz gibi algoritmaları tercih ederken zaman ve hafıza karmaşıklıklarına bakarız. Bu karmaşıklıkları buradan inceleyebiliriz.

Peki biz bu iki algoritmadan birini kullanmak istersek, hangisini tercih etmeliyiz? Benim araştırmalarıma göre Merge sort, Heap sort algoritmasına göre hafızayı daha az kullandığı için kısıtlı hafıza alanlarında tercih edilmelidir deniyor.

Şu sayfada bahsedilen iki algoritmayı test edebiliyoruz. Birkaç denemede Merge Sort algoritmasının daha hızlı olduğunu gördüm. Ancak zaman karmaşıklığı aynı olduğu halde neden Merge Sort çoğunlukla üstün geliyor?

1 Beğeni

Cunku zaman karmasikligi en iyi / en kotu / ortalama performansi veriyor, her defasinda olacak performansi degil.

n sonsuzda giderkenki (asemptotik) performans degisikligini veriyorlar, performans olcusunu de degil.

Her algoritmanin iyi ve kotu calistigi girdiler var, ve bu girdiler algoritmaya gore degisiyor.

O(n^2) iki algoritma ayni hizda calismak zorunda degil. O(n) bir algoritmadan yavas calismak zorunda da degiller.

1 Beğeni

Yani sadece bunlara bağlı değil, aynı zamanda algoritmanın gerçekleştirilmesine de bağlıdır diyorsunuz. Doğru mu anladım?

Performans mi? Havanin sicakligina bile bagli.

Soyle bir ornek vereyim:

def sort1(xs): 
    return merge_sort(xs)

def sort2(xs):
    if is_sorted(xs):
        print("oh, gerek kalmadi")
        return xs
    else:
        return merge_sort(xs)

is_sorted = lambda xs: all([a<=b for a,b in zip(xs, xs[1:])]) # O(n)

sort1 de sort2 de O(n*log(n)).

Cogunlukla sort1 daha hizli cunku ekstradan is_sorted cagirmiyor. Fakat sirali listelerde sort2 daha hizli cunku merge_sort cagirmiyor.

Sirali listelerdeki calisma performanslarina bakarsak sort2 O(n).

2 Beğeni

Optimize edilirse aynen sizin dediğiniz gibi O(n) gibi karmaşıklıklara inebiliyor, tıpkı bubble sort gibi.
Peki heap sort vs merge sort hakkında fikriniz nedir? Hangi durumlarda kullanılabilir ikisinden biri?

Bir kisim girdi icin optimizasyon (cogunlukla) baska bir kisim girdi icin pesimizasyon getiriyor, onu soylemeye calisiyorum.

Merge vs heap (vs digerleri)? Bilmiyorum.
Data setini temsil eden bir subset aliyorsun, butun sort algoritmalarini calistirip deniyorsun. En guzel calisani seciyorsun.

(Sonra review esnasinda “gunde bes milisaniye icin kodun okunabilirligini azaltmana degmez” diyorum, standart kutuphanenin default sort’una geri donuyoruz)

2 Beğeni

Konuya yazmanızı bekliyordum :smiley: Yorumlarınız için teşekkür ederim, sağolun.

Bu pakete bakmak isteyebilirsiniz.

1 Beğeni

Algoritmalardan yana problem yok. Bunların nerede ve nasıl kullanılacağını tartışıyoruz. Hazır paket yerine kendim yazıyorum. Teşekkür ederim.