Matematik asoslar va raqamli modellashtirish usullari

2010 Yil, T. 2, № 3, P. 231-272
238
Va Karpov
goritmov. To'g'ri baholarni olish uchun siz bitta
nazariy model tizimidan foydalanishingiz kerak.
2. Taqqoslash
T
A
(n) va T
B
(n) nazariy modelda n ning kichik qiymatlari bo'lishi mumkin, ammo
foydasiz. O'lchov parametrining kichik qiymati uchun hatto samarasiz algoritm
tezda amalga oshiriladi. Agar ulardan biri ishlayotgan bo'lsa, foydalanuvchi uchun algoritmlarni bajarish vaqtlarida sezilarli farq yo'q
0.5 soniya, ikkinchisi esa 0.1 soniya. Taqqoslash
a va b samaradorligi yuqori qiymatlar bilan amalga oshirilishi kerak
n, ideal holda n
→ ∞.
3. Biz haqiqiy qiymatlarni taqqoslashdan manfaatdormiz
T
A
(n) va T
B
(n) katta
n va ularning o'sish sur'atlarini taqqoslash. Agar T
A
(n) = 10
6
× n
2
, va
T
B
(n) = n
3
, keyin
n
< 10
6
algoritm b yanada samarali, ammo
n
> 10
6
A algoritmi yanada samarali bo'ladi.
Boshqacha qilib aytadigan bo'lsak, biz taqqoslaymizasimptotik xatti-harakatlar
algoritmlar uchun
n
→ ∞ kompyuterning nazariy modelida.
Keyinchalik taqdim etish uchun biz
funktsiyalarning xatti-harakatlarini asimptotik tahlil qilishda ishlatiladigan ba'zi standart ro'yxatga olish shakllariga muhtojmiz. Ikkita
xususiyat mavjud deb taxmin qiling
f va g tamsayı ijobiy argument n dan, ijobiy qabul
qadriyatlar. Keyin:
O1.1.
f
(n) = O(g (n)) keyin va faqat ijobiy sobit c va n mavjud bo'lganda
0
bunday
f
(n)
n ≥ n 0 da ≤ cg(n) ;
O1.2.
f
(n) = ō (g (n)) keyin va faqat ijobiy sobit c va n mavjud bo'lganda
0
bunday
cg
(n)
n ≥ n 0 da ≤ f (n) ;
O1.3.
f
(n) = Θ(g (n)) keyin va faqat ijobiy sobit C mavjud bo'lganda
1
,
c
2
va
n
0
bunday
c
1g(n)
n ≥ n 0 da ≤ f (n) ≤ C 2 g(n).
E'tibor bering, agar
f
(n) = Θ(g (n)), keyin f(n) = o(g (n)) va F(n) = ō(g (n)).
Keling, bir qator ta'riflarni beramiz.
Unga ruxsat bering
T
A
(n) va T
B
(n) - bir xil hisoblash tizimida ishlash vaqti-
tergovchi NY algoritmlar a va b mos ravishda, va
T
0
(n) -
xuddi shu vazifani hal qilish uchun o'zboshimchalik bilan ketma-ket algoritmning pastki qismidagi ish vaqtini nazariy baholash,
ya'ni.
T
0
(n) = ō(T (n)) har qanday algoritm uchun. Keyin aytamizbirinchi
O2.1. Agar
T
A
(n) = O(T
B
(n)), xatti-harakatlar uchun a algoritmi b algoritmidan ham yomon emas.
O2.2. Agar
T
A
(n) = Ω(T
B
(n)), a algoritmining xatti-harakati B algoritmidan yaxshiroq emas.
O2.3. Agar
T
A
(n) = Θ(T
B
(n)), A va b algoritmlari xatti-harakatlar bilan bir xil.
O2.4. Agar
T
A
(n) = Θ(T
0
(n)), A algoritmi maqbuldir.
Bunday holda, har doim eng yomon kirish ma'lumotlari uchun o'lchanadi.
Ketma-ket algoritmlarning ish vaqtini baholash uchun odatda
RAM (Random Access Machine) deb ataladigan hisoblash tizimi modeli qo'llaniladi. Uning xatti
-harakati quyidagi xususiyatlar bilan tartibga solinadi.
1. Tizimda bitta yadroli (bitta ijrochi) bitta protsessor mavjud.
2. O'qish va yozish uchun xotira xujayralari tasodifiy tartibda mavjud.
3. Xotiraga kirish vaqti bor Θ
(1) qat'i nazar, kirish operatsiya o'qish hisoblanadi
yoki yozuv.
4. Ijrochining asosiy operatsiyalarini bajarish vaqti Θ
(1).
Asimptotik vaqtni baholash qanday amalga oshirilayotgani haqida oddiy misolni ko'rib chiqing
algoritm ishi. Tanlash vazifasini oling.
Ko'p narsani oling
S
=
{s
1
, s
2
, . . . , s
n
}, bu erda lineer tartib belgilanadi, ya'ni to'siqning har
qanday ikkita elementi uchun aniqlanishi mumkin: ular teng yoki boshqasidan kamroq.