Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
239
Unvon elementi
k,
1
≤ k ≤ n, s to'plami uchun s
i
. agar shunday bo'lsa
k-m
bu to'siqning eng kichik elementi. Unvonning aniq ta'rifi uchun, agar
s
i
= s
j
,
i
< j, keyin s
i
u kamroq darajaga ega
s
j
.
1-darajali element to'plamda minimal qiymatga ega. Unvon elementi
n-Maxi-
mal qiymati. Unvon elementi
n
/2 (
- butun yuqoriga yaxlitlash) median
majmui deb ataladi. To'plamning medianasi ajoyib xususiyatga ega: to'siqda
kam emas
n
/ O'rtacha qiymatdan yuqori yoki unga teng bo'lgan 2 ta element va kamida n / 2
ushbu qiymatdan oshmaydigan elementlar.
Tanlash vazifasi-bu elementning qiymatini unvon bilan topishdir
S to'plamida k. Albatta,
muammoni ahamiyatsiz hal qilish mumkin:
elementlarning qiymatlarini oshirish va kerakli qiymatni tanlash uchun bizning to'plamimizni tartiblashtiramiz. Biroq, bu ortiqcha
ishni bajarishni o'z ichiga oladi — biz og'irlik darajasiga muhtoj emasmiz, biz bir qiymatga muhtojmiz.
Biz boshqa yo'l bilan boramiz. Ushbu muammoni hal qilish uchun oddiy rekursivni oling
besh bosqichdan iborat algoritm [Aki, 1989].
Step1. Agar kuch-quvvat bo'lsa
S kichik sobit —
|S/ < q,
keyin kerakli qiymatni setlarni tartiblash orqali qidiramiz (o'lchov parametrining kichik qiymati
bilan bu joizdir). Qiymati
q keyinchalik aniqlanadi. Aks holda, natijani buzamiz-
bu juda ko'p
|S / / q kichik guruhlar S
i
, har birida, bundan mustasno, mavjud bo'lishi mumkin,
ikkinchisi esa kiradi
q elementlar.