- Agar kirish massivining elementlari tasodifiy tartibda joylashtirilgan bo'lsa, u holda biz o'rtacha ikkiga bo'linishga yaqin bo'lgan qismlarga ega bo'lamiz, shuning uchun tezkor saralashning ishlash vaqti D (njurnal2n).
- Yaxshi bo'linish imkoniyatini oshirish uchun siz tasodifiy ravishda pivotlarni tanlashingiz mumkin.
- Bundan tashqari, Quicksort protsedurasi elementlarni necha marta almashtirishini taxmin qilishingiz kerak. Aksariyat almashinuvlar qachon sodir bo'ladinjuft va kirish massivi shaklga egan,n-2,n-4,...,4,2,1,3,5,...,n-3,n-1. Bunday holda, u amalga oshiradin2/4 almashinadi va algoritmning asimptotik ish vaqti eng yomon holatga mos keladi t(n2).
Xulosa
Saralash vaqtini yengish mumkinmi D(njurnal2n)?
YO'Q
Agar elementlarni joylashtirish tartibini aniqlashning yagona yo'li ularni solishtirish bo'lsa
HA
Saralanadigan elementlar haqida qo'shimcha ma'lumot mavjud bo'lsa
Taqqoslash bo'yicha saralash
(tartib tartibini faqat juft elementlarni solishtirish orqali aniqlaydi)
Ō(njurnal2n)
ekzistensial pastki chegara
(chunki bunday kirish mavjud)
Ō(n)
universal pastki chegara (chunki u barcha kirishlar uchun amal qiladi)
Vaqt bo'yicha oddiy tartiblash t(n)
- Faraz qilaylik, har bir tartiblash kaliti bitta yoki ikkitadir.
- Keling, barcha elementlarni ko'rib chiqamiz va ular orasida nechta (k) borligini hisoblaymiz.
- Massivning birinchi k pozitsiyasiga 1 qiymatini, qolgan qismiga esa 2 qiymatini o'rnatingn-k pozitsiyalari.
- Algoritm hech qachon ikkita massiv elementini bir-biri bilan solishtirmaydi: har bir massiv elementini 1 qiymati bilan solishtiradi, lekin massivning boshqa elementi bilan emas.
- Jarayon T(n) vaqtida bajariladi, chunki birinchi sikl n ta takrorni amalga oshiradi, xuddi oxirgi ikkita tsikl birgalikda.
- Bu. massivning elementlari haqida qo'shimcha ma'lumot mavjud bo'lsa, solishtirish tartiblash algoritmlarini urish mumkin.
Do'stlaringiz bilan baham: |
