, iki yolRasgele hızlı Rasgele hızlı uygulanması için
Yöntem 1: rastgele bir pivot seçimi
Method2: giriş rasgele bir permütasyon oluşturma ve eksen
birinci eleman seçen bir Quicksort beslemekYöntem1, yöntem2 ile rasgeleleştirme bakımından aynı mıdır?
Not: Yöntem2'nin tüm bölümleri eşit şekilde oluşturmasına karşın, yöntem1'in üretmediğine bakar. Yani eğer aynı değilse, o zaman performans etkisinin ne olduğunu anlamak istiyorum.
Evet. Her iki durumda da, pivot olarak seçilen herhangi bir belirli elemanın olasılığı 1/len'dir (giriş). (Ancak, ikinci yöntem, rasgele permütasyon oluşturmak için ekstra bir doğrusal geçiş gerektireceğinden, sabit bir faktör tarafından neredeyse kesinlikle daha yavaştır.)
Ama belirli bir giriş için, 2. yöntem tüm n'ye sahip! permütasyonlar aynı derecede olasıdır, ancak 1. yöntem, girişin göreli sıralamasını değiştirmez, bu yüzden bir girdi için tüm olası bölümleri içermez. Bu yüzden bir fark olduğunu hissediyorum, ama ne etkisi olacağını emin değilim. –
"Tüm olası bölümler" ile ne demek istediğinden emin değilim. Pivot elemanından daha büyük veya daha küçük olan elemanlar dizisi, emirlerine bağlı değildir. – jacobm
Üzgünüm kafam karıştı, şimdi anlıyorum. Teşekkürler –
Evet derdim. Her adımdaki ikili bölüm, her iki yöntemde de aynı yasayı takip etmektedir. –