|
Qadam 2. Har bir kichik to'plamda
S
i
tartiblash orqali biz uni medianga qidiramiz
m
i
.
Step3. Topilgan medianlardan biz juda ko'p qurmoqdamiz
M
=
{m
1
, m
2
, . . . , m
|S|/q
}. Recursivno
topish
m
0
- juda ko'p median
M.
Step4. Asl majmui
S quyidagi uchta l, E va G pastki qismiga bo'linadi
shunday qilib:
L
: s
i
∈ L ↔ s
i
< m
0
E
: s
i
∈ E ↔ s
i
= m
0
G
: s
i
∈ G ↔ s
i
> m
0
Qadam 5. Agar
|L / ≥ k, keyin kerakli element l to'plamida va biz recursively
unvon elementini topish uchun algoritmimizni ishga tushiramiz
l majmui ichida k. Aks holda, agar
|L | + | e / ≥ k, kerakli element e setiga tegishli va uning qiymati m
0
. Agar
|L / + / E / < k bo'lsa, bizning elementimiz g majmuasiga kiradi va biz ushbu to'plamda
unvon elementini izlaymiz
k
− |L| − |E|.
Ish vaqtini baholang
T
(n) yuqoridagi algoritm.
Step1. Agar
/ S / < q, keyin vaqt ichida kerakli qiymatni topamiz Θ (1). Aks holda
to'siqni ajratish uchun
S haqida
|S / / q kichik guruhlar bizga vaqt kerak bo'ladi c
1
∗ |S| = c
1
∗ n. Uchun
birinchi qadam
T
1
(n) = c
1
∗ n.
Qadam 2. Har bir mediani qidirish vaqti Θ
(1), lekin bizda bunday median bor
|S/ / q qismlari.
Shuning uchun, ikkinchi qadam uchun ish vaqtini baholash
T
2
(n) = c
2
∗ |S| = c
2
∗ n.
Step3. Kuch-quvvat
M bor
|S|/q . Ushbu to'plamda mediani topish uchun biz
vaqt sarflaymiz
T
3
(n) = T (
|S|/q ) = T (n/q).
Step4. Setlarni qurish uchun
L, e va g biz har bir element asl kerak
to'plamlar qiymati bilan taqqoslanadi
m
0
. Shuning uchun, bu qadam uchun
T
4
(n) = c
3
∗ n.
Qadam 5. Agar kerakli element juda ko'p bo'lsa
E, keyin yechim allaqachon mavjud-vaqt Θ
(1).
Aytaylik, u juda ko'p edi
L. Biz kuch-qudratni baholaymiz l yuqori qismida. M majmui ichida
kamida
|M/ / 2 = n / (2 q) elementlar m
i
cheksiz yoki teng
m
0
. Har bir sotda-
filiallar to'plami
S
i
kamida
|S
i
//2 = s to'plamining q / 2 elementlari
teng
m
i
. Shuning uchun ,
|G| + |E| ≥ n/(2q) × q/2 = n/4 . Shuning uchun| L/ ≤ 3 n / 4. Shunga o'xshash
2010 Yil, T. 2, № 3, P. 231-272
240
Va Karpov
yuqori baholarni olish mumkinva kuch-quvvat uchun
G. Shuning uchun, bu ish vaqti
qadamlar baholanishi mumkin, qanday qilib
T
5
(n) = T (3n/4).
Nihoyat
T
(n) = T
1
(n) + T
2
(n) + T
3
(n) + T
4
(n) + T
5
(n) = c
4
∗ n + T (n/q) + T (3n/4).
(2.1)
Bunday tenglamaning qat'iy echimi juda ko'p vaqt talab qiladi, shuning uchun biz ba'zi
samarasiz "shaman raqslari" ga murojaat qilamiz.
"Shaman raqsi" 1. Unga ruxsat bering
n
/q + 3 n/ 4 < n, keyin q
≤ 5. Q = 5 qo'ying. Bizda bor
T
(n) = c
4
∗ n + T (n/5) + T (3n/4).
"Shaman raqsi" 2. Buni tasavvur qiling
T
(n)c
5
∗ n. Keyin c bilan
5
= 20
∗ c
4
qabul qiling
T
(n)c
4
∗ n + 20 ∗ c
4
∗ n/5 + 60 ∗ c
4
∗ n/4 = c
5
∗ n. Bu taxmin tenglamaga zid emas va,
shunday qilib,
T
(n) = O(n).
Biz algoritm ish vaqti quyida nazariy baholash topish. Topish uchun
unvon bilan elementning qiymati
k, biz kamida bir marta qarashimiz kerak barcha elementlarning qiymatlari.
Shuning uchun
T
(n) = ō (n) va nihoyat T(n) = Θ (n). Ko'rib chiqilgan algoritm ham shunday bo'ldi
eng yaxshi.
(2.1) kabi munosabatlarni to'g'ri hal qilish uchun asosiy teoremadan foydalaning
asimptotik tahlil.
Agar
T
(n) = aT (n / b) + f (n), bu erda a va b sobit, a
≥ 1, b > 1, f ( n) > 0 va n qabul qiladi
barcha salbiy qadriyatlar, keyin:
1. agar
f
(n) = O(n
log
b
a
−ε
), bu erda doimiy e > 0, keyin T(n) = Θ (N
log
b
a
);
2. agar
f
(n) = Θ(n
log
b
a
keyin T(n) = Θ (N
log
b
a
log n);
3. agar
f
(n) = O(n
log
b
a
+ε
), bu erda e > 0 sobit va C va N sobit, 0 < c < 1,
N
> 0, bunday (n/b) > n af (n/b)
≤ cf( n), keyin T (n) = Θ(f (n)).
Teoremaning isboti [Miller, Boxer, 2006] da mavjud bo'lib, u erda 10
betlik toza matnni oladi. Tenglama (2.1) teoremasi uchun to'g'ridan-to'g'ri qo'llanilmasa-da
, uning isbotiga o'xshash tarzda "shamanlik raqslari"ni qat'iyan oqlash mumkin.
Parallel algoritmlarning ish vaqtini baholash uchun hisoblash tizimining eng oddiy modeli
RAM modelini umumlashtirishdir, bu odatda belgilanadipram (Parallel tasodifiy kirish
mashinasi). Uning asosiy xususiyatlari:
1. Tizimda ko'plab protsessorlar va / yoki yadrolar mavjud (bir nechta ijrochilar)
2. O'qish va yozish uchun xotira xujayralari o'zboshimchalik bilan mavjud
3. Xotiraga kirish vaqti bor Θ
(1) qat'i nazar, kirish operatsiya o'qish hisoblanadi
yoki yozuv.
4. Ijrochining asosiy operatsiyalarini bajarish vaqti Θ
(1).
Muammoning miqyosi parametridan tashqari, muammoni hal qilish uchun parallel algoritmlar
n bor
opsiyonel o'lchov parametri
N-ular bilan shug'ullanadigan ijrochilar soni
amalga oshirish.
Ijrochilar sonini aniqlang
N . Keyin
bir xil parallel hisoblash tizimida ishlaydigan ikkita parallel a va B algoritmlari
uchun O2.1–O2.3 ta'riflariga o'xshash ta'riflarni kiritishingiz mumkin.
O2.5. Agar
T
A
(n) = O(T
B
(n)), parallel algoritm A xatti-harakati B algoritmidan ham yomon emas.
O2.6. Agar
T
A
(n) = Ω(T
B
(n)), parallel algoritm A xatti-harakati algoritm b dan yaxshiroq emas.
O2.7. Agar
T
A
(n) = Θ(T
B
(n)), parallel algoritmlar a va b xatti bir xil bo'ladi.
Do'stlaringiz bilan baham: |
