1
Мавзу 2.
Алгоритмлар тахлили.
"A" shahridan "B" shahriga borishni ko'p usullar bilan amalga oshirish mumkin:
samolyotda, avtobusda, poezdda, shuningdek, velosipedda.
Mavjud usullar
va ularning qulayligiga qarab, biz o'zimizga mos keladigan
usulni tanlaymiz.
Xuddi
shu singari, informatika fanida biror bir masalani yechish uchun bir
nechta algoritmlar mavjud (masalan, saralash masalasida qo‘shish
orqali saralash,
tanlash orqali saralash, tezkor saralash va boshqalar kabi ko‘plab algoritmlar mavjud).
Algoritm tahlili turli algoritmlarning hisoblash vaqti va kompyuter xotirasidan
egallaydigan joyi nuqtai nazardan qanchalik samarali ekanligini
aniqlashga yordam
beradi.
Algoritm tahlilining maqsadi algoritmlarni (yoki yechimlarni) asosan bajarilish
vaqti va boshqa omillar (masalan,
xotira hajmi, algoritm murakkabligi va boshqalar)
boʻyicha solishtirishdir.
Bajarilish vaqti tahlili nima?
Bu masala hajmi ortishi (kiritish ma'lumotlari hajmi oshganda) bilan bajarilish
vaqti qanday oshishini aniqlash jarayonidir. Kirish ma'lumotlarining o'lchami -
kirishdagi elementlarning soni bo'lib, u masalani va berilganlarning turlariga bog'liq.
Kirish ma'lumotlari har xil turdagi bo'lishi mumkin.
Quyida keng tarqalgan kirish ma'lumotlari turlari keltirilgan.
•
Massiv hajmi
• Polinom darajasi
• Matritsadagi elementlar soni
• Berilganlarning ikkilik ko'rinishidagi bitlar soni
• Grafning uchlari va qirralari soni.
Algoritmlarni qanday solishtirish mumkin?
Algoritmlarni solishtirish uchun bir nechta ob'ektiv ko'rsatkichlardan
foydalaniladi:
Bajarilish vaqti. Bu eng yaxshi ko'rsatkich emas, chunki bajarish vaqti aniq bir
kompyuter arxitekturasiga bog'liq.
Bajarilgan amallar soni. Bu ham yaxshi o'lchov emas, chunki bajarilgan amallar
soni ba'zi shartlarga qarab farq qilishi mumkin.
Dasturlash
tilini tanlash, shuningdek, individual
dasturchi tomonidan dastur
yozish uslubi.
2
Umumiy qabul qilingan eng yaxshi yechim quyidagi usul hisoblanadi:
Aytaylik, ma'lum bir algoritmning bajarilish vaqti masalaning kirish hajmi - n
(ya'ni f (n)) funktsiyasi sifatida aniqlangan va turli bajarilish usullariga mos keladigan
ushbu turli funktsiyalarni taqqoslash.
Bunday taqqoslash
usuli mashina vaqtiga, dasturlash uslubiga va boshqa
parametrlarga bog'liq emas.
