Algoritmlar murakkabligining oʻsish tartibi
Murakkablikning oʻsish tartibi
(yoki aksiomatik murakkablik)
katta kirish hajmi uchun algoritmning murakkablik funksiyasining
taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt
murakkabligini baholashda elementar amallarni koʻrib chiqishning hojati
yoʻq, algoritm qadamlarini koʻrib chiqish kifoya.
Algoritm qadami
– bu ketma-ket joylashtirilgan elementar amallar
toʻplami, uning bajarilish vaqti kirish qadamiga bogʻliq emas, ya‘ni
yuqoridan qandaydir doimiy bilan chegaralangan.
Asimptotik baholashning koʻrinishlari.
F(n)>0 murakkabligini,
bir xil tartibdagi g(n)>0 funksiyasini, kirish n>0 oʻlchamini koʻrib
chiqaylik.
Agar f(n) = O (g(n)) va n> n
0
uchun c>0, n
0
> 0 konstantalar mavjud
boʻlsa, u holda 0
18
Bu holda g(n) funksiyasi f(n) uchun asimptotik-aniq baho
hisoblanadi. Agar f(n) algoritmning murakkablik funksiyasi boʻlsa, unda
murakkablik tartibi f(n) uchun - O(g(n)) deb belgilanadi. Ushbu ibora
doimiy koeffitsiyentgacha g(n) dan tez oʻsmaydigan funksiyalar sinfini
belgilaydi.
1-jadval.
Asimptotik funksiyalarga misollar
1.4. Algoritmlarning yomon, oʻrta, yaxshi holatlari tushunchalari
Algoritm murakkabligining oʻsish tartibi O(n) deb aytganda
nimani nazarda tutamiz? Bu oʻrtacha? Yoki eng yomoni? Ehtimol,
eng yaxshisi?
Agar eng yomon holat va oʻrtacha koʻrsatkichlar bir-biridan farq
qilmasa, odatda, eng yomon holat nazarda tutiladi. Masalan, biz oʻrtacha
O(1) oʻsadigan, lekin vaqti-vaqti bilan O(n) ga aylanadigan
algoritmlarning misollarini koʻrib chiqamiz (masalan, massivga element
qoʻshish). Bunday holda, algoritm oʻrtacha vaqt ichida doimiy ishlashini
koʻrsatamiz va murakkablik oshadigan holatlarni tushuntiramiz.
Algoritmlar
va
ma‘lumotlar
tuzilmalarining
murakkabligini
oʻlchashda odatda ikkita narsa haqida gaplashamiz: ishni bajarish uchun
zarur boʻlgan amallar soni (hisoblash murakkabligi) va algoritm zarur
boʻlgan resurslar, xususan, xotira (fazoviy murakkablik).
Oʻn baravar tezroq ishlaydigan, ammo oʻn barobar koʻproq joy
ishlatadigan algoritm koʻproq xotirali server mashinasi uchun yaxshi
f(n)
g(n)
8
1
19
boʻlishi mumkin. Ammo xotira hajmi chekli oʻrnatilgan tizimlarda
ushbu algoritmdan foydalanib boʻlmaydi.
Odatda, quyidagi amallar hisobga olinadi:
1)
taqqoslashlar ("katta", "kichik", "teng");
2)
oʻzlashtirish (ta‘minlash);
3)
xotira ajratish.
Qaysi amalni hisoblash esa, odatda kontekstda aniqlanadi.
Masalan, ma‘lumotlar tarkibidagi elementni topish algoritmini
tavsiflashda biz deyarli taqqoslash amallarini nazarda tutamiz. Qidirish,
avvalambor, oʻqish jarayonidir, shuning uchun ta‘minlash yoki xotira
ajratishda hech qanday ma‘no yoʻq.
Tartiblash haqida gapirganda esa, taqqoslash, xotira ajratish va
ta‘minlash amallarini hisobga olishimiz mumkin. Bunday hollarda biz
qaysi amallarni koʻrib chiqayotganimizni aniq koʻrsatib beramiz.
Algoritmlar nazariyasining asoslarini bilish har qanday dasturchi
uchun juda muhimdir, chunki aynan shu fan algoritmlarning umumiy
xususiyatlarini va ularni namoyish etishning rasmiy modellarini
oʻrganadi. Hatto informatika darslaridan boshlab ham bizga jadvallarni
tuzishni oʻrgatmoqdalar, bu keyinchalik maktabga qaraganda ancha
murakkab masalalarni yozishda yordam beradi. Bundan tashqari,
ma‘lum bir muammoni hal qilishning deyarli har doim bir necha yoʻli
borligi sir emas: ba‘zilari koʻp vaqt, boshqa resurslarni sarflashni oʻz
ichiga oladi, boshqalari esa faqat taxminiy yechim topishga yordam
beradi.
Siz har doim topshiriqqa muvofiq ravishda eng maqbul narsani
izlashingiz lozim, xususan, muammolar sinfini hal qilish algoritmlarini
ishlab chiqishda.
Algoritmni har xil hajm va miqdorlarning boshlangʻich qiymatlari
bilan qanday ishlashini, qanday manbalarga ehtiyoj borligini va yakuniy
natijani chiqarish uchun qancha vaqt ketishini baholash ham muhimdir.
Koʻpincha, algoritm tahlili bir xil masalani yechish uchun ikki xil
algoritmlarni taqqoslash yoki algoritmning amaliy qoʻllanilishini
aniqlash uchun ishlatiladi. Algoritmlarni bajarish vaqti boʻyicha
baholashga
toʻxtalamiz.
Algoritmlarni
bajarish
vaqtiga
qarab
20
baholashning
yondashuvlaridan
biri
bu
algoritmni
oddiygina
kompyuterda ishga tushirish va uni u yoki bu tarzda vaqtga solishdir.
Ushbu yondashuvning koʻplab kamchiliklari mavjud. Birinchidan,
bajarish vaqti algoritm ishlayotgan kompyuterga juda bogʻliq.
Ikkinchidan, bunday taxmin kiritish ma‘lumotlarining ma‘lum bir
oʻlchovi uchun faqat bitta qiymatni beradi. Agar bizda har xil oʻlchovlar
boʻyicha taxminiy jadval mavjud boʻlsa ham, undan ish vaqtining kirish
ma‘lumotlarining oʻlchamiga funksional bogʻliqligini olish juda
muammoli.
Shuning uchun algoritmni bajarilish vaqti boʻyicha baholash uchun
kirish ma‘lumotlarining oʻlchamlari boʻyicha bajarilgan elementar
amallar sonining funksional bogʻliqligini topishga harakat qilishdir.
Algoritm murakkabligining asosiy koʻrsatkichi bu muammoni hal
qilish uchun sarflanadigan
|
