O(n log n) da medianani topish

Ro‘yxatning medianasini topish arzimas ishdek tuyulishi mumkin, ammo uni chiziqli vaqtda bajarish jiddiy yondashuvni talab qiladi. Ushbu postda men o'zim yoqtirgan algoritmlardan biri haqida gapiraman - medianalar medianasidan foydalangan holda deterministik chiziqli vaqt ichida ro'yxatning medianasini topish. Garchi ushbu algoritm chiziqli vaqtda ishlashini isbotlash juda qiyin bo'lsa-da, maqolaning o'zi algoritmlarni tahlil qilish bo'yicha dastlabki bilim darajasiga ega bo'lgan o'quvchilarga tushunarli bo'ladi.

O(n log n) da medianani topish

Medianani topishning eng oddiy usuli bu ro'yxatni tartiblash va indeks bo'yicha medianani tanlashdir. Taqqoslash bo'yicha eng tez tartiblash O(n log n) ni oladi, shuning uchun bajarilish vaqti1, 2 bunga bog'liq.

Bu usul eng oddiy kodga ega, lekin bu, albatta, eng tez emas.

O'rtacha vaqt ichida medianani topish O(n)

Bizning keyingi qadamimiz, agar omadimiz kelsa, chiziqli vaqt bo'yicha o'rtacha medianani topishdir. Bu “quickselect” deb nomlangan algoritm Toni Xoar tomonidan ishlab chiqilgan bo‘lib, u ham xuddi shunday nomli tezkor saralash algoritmini ixtiro qilgan. Bu rekursiv algoritm va u har qanday elementni (faqat medianani emas) topa oladi.

Keling, ro'yxatning indeksini tanlaymiz. Tanlash usuli muhim emas, amalda u juda mos va tasodifiy. Ushbu indeksdagi elementi (pivot) deb ataladi.

Keling, ro'yxatni ikki guruhga ajratamiz:

Elementlar pivotdan kichik yoki unga teng, lesser_els

Elementlar pivotdan kattaroq, great_els

Biz bilamizki, ushbu guruhlardan biri medianani o'z ichiga oladi. Faraz qilaylik, biz k elementni qidiramiz:

Agar lesser_els ichida k yoki undan ortiq elementlar mavjud boʻlsa, k. elementni qidirib, kamroq lesser_els roʻyxatini rekursiv aylantiring.

Agar lesser_els ichida k elementdan bo'lsa, rekursiv ravishda greater_els ro'yxatidan o'ting. K ni qidirish o'rniga biz k-len (lesser_els) ni qidiramiz.

Keling, quyidagi ro'yxatni olaylik. Biz medianani topmoqchimiz.