O(n log n) da medianani topish

l = [9,1,0,2,3,4,6,8,7,10,5]

len(l) == 11, shuning uchun biz oltinchi eng kichik elementni qidiramiz

Avval biz mos yozuvlar elementini (pivot) tanlashimiz kerak. Biz tasodifiy indeks 3 ni tanlaymiz.

Ushbu indeksdagi elementning qiymati 2 ga teng.

Ro'yxatni pivot bo'yicha guruhlarga ajratamiz:

[1,0,2], [9,3,4,6,8,7,10,5]

Bizga oltinchi element kerak. 6-len (left) = 3, shuning uchun bizga kerak o’ng qatordagi uchinchi eng kichik element. Endi biz quyidagi massivdagi uchinchi eng kichik elementni qidiramiz:

[9,3,4,6,8,7,10,5]

Biz o'zimizning asosiy omilimiz bo'lish uchun tasodifiy indeksni tanlaymiz.

Biz indeks 2 ni tanladik, uning qiymati l[2]=6

Pivot bo'yicha biz guruhlarga ajratamiz:

[3,4,5,6] [9,7,10]

Biz uchinchi eng kichik elementni xohlaymiz, shuning uchun u chap massivdagi uchinchi eng kichik element ekanligini bilamiz

Quickselect bilan medianani topish uchun biz tezkor tanlashni alohida funksiyaga ajratamiz. Quickselect_median funksiyamiz kerakli indekslar bilan quickselectni chaqiradi.

Endi biz quyidagi massivda uchinchi eng kichigini qidirmoqdamiz:

Median topish algoritmlari ( chiziqli vaqtni tanlash algoritmlari) o'lchamining Saralanmagan ro'yxatidagi eng kichik sonni samarali hisoblash uchun bo'linish va zabt etish strategiyasidan foydalaniladi. n, bu yerda 1 va n orasidagi butun son. Tanlov algoritmlari ko'pincha qism sifatida ishlatiladi masalan, ular quicksort-da pivotni tanlashda yordam berish uchun ishlatiladi va shuningdek, ro'yxatdagi maksimal, minimal va median elementlar kabi buyurtma statistikasini aniqlashda ishlatiladi.

 

Reja:

1. Medianni topish algoritmi

2. Median-of-medians algoritmi

3. Medianni topish algoritmini amalga oshirish

4.Median-of-medians algoritmining murakkabligi

Xulosa

Mediani topish algoritmi echadigan muammo quyidagicha:

Ushbu muammoni, albatta, raqamlar ro'yxatini saralash va indeksidagi qiymatni qaytarish uchun saralash algoritmi yordamida hal qilish mumkin. Biroq, ko'plab saralash algoritmlari nlogn vaqtidan tezroq o'tolmaydi. Medianani topish algoritmi ro'yxatdagi eng kichik elementini O(n) vaqtda topishi mumkin.