Chewy Mesaj tarihi: Ekim 23, 2011 Mesaj tarihi: Ekim 23, 2011 Soru şu aynen : Suggest how any sorting algorithm can be augmented in a way to make the best-case count of its key comparisons equal to just n−1 (n is a list’s size, of course). Do you think it would be a worthwhile addition to any sorting algorithm? Şu soruyu bir açın bana yaw :D Nasıl geliştirebilir demiyor mu best case count karşılaştırması için ? Yani mesela ilk önce sorting algoritması bakıcak sıralı gelmiş hiç ellemiycek mi nolcak kafam karıştı :S
Deacon Mesaj tarihi: Ekim 23, 2011 Mesaj tarihi: Ekim 23, 2011 Diyor ki herhangi bir sorting algoritmasinin best case'ini n-1 karsilastirma yapicak sekilde degistiricek bir yol soyleyin. Sonra da ekliyor bunu herhangi bir sorting algoritmalarina eklemek mantikli midir, deger mi ekledigimize?
Chewy Mesaj tarihi: Ekim 23, 2011 Konuyu açan Mesaj tarihi: Ekim 23, 2011 e zaten hepsi n-1 comparison yapmıyor mu ? :D
Deacon Mesaj tarihi: Ekim 23, 2011 Mesaj tarihi: Ekim 23, 2011 O dedigin dogru olsaydi O(n) calisan comparison based sort algoritmalarimiz olurdu ki matematiksel olarak lower bound'un nlogn oldugu gosterildi :p Ilk mesajinda cevabi yazmissin aslinda. Tam anlamamissin galiba sen sorting olayini?
Chewy Mesaj tarihi: Ekim 23, 2011 Konuyu açan Mesaj tarihi: Ekim 23, 2011 valla kafam iice karıstı suan :S
riglous Mesaj tarihi: Ekim 23, 2011 Mesaj tarihi: Ekim 23, 2011 Bak şimdi sorting algoritmalarında sen n defa tüm node'ların üzerinden geçiyorsun bir kere. Bunu yaparken bir yandan da gelen node'ları karşılaştırıyorsun ki bu da logn sürüyor, binary tree olursa. Sonuç olarak senin algoritman O(n logn) oluyor. Sana diyor ki bunu herhangi bir sorting algoritmasına eklemek mantıklı mı? Bence değil, best case'i n yapması worst case'in de öyle olduğu anlamına gelmez. Algoritmanın hızı worst case üzerinden hesaplanır. Haliyle mantıklı değil. Öte yandan eğer algoritma n'den daha uzun bir sürede yapıyorsa işini, O(n n^2) gibi bir şeyse o zaman eklemek belki performans açısından yararlı olabilir.
Öne çıkan mesajlar