Mustaqil ish mavzu: Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik solishtirma mezonlar

Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Algoritmlarni loyihalash fanidan.
MUSTAQIL ISH


Mavzu: Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik solishtirma mezonlar.

Guruh: 050-19

Bajardi: Umarov M
Tekshirdi: Mamadaliyev X

Toshkent 2022

Reja:

• 
  Samaradorlik ko’rsatkichlari.
  
• 
  Algoritmlarni murakkabligini aniqlash.
  
• 
  Hisoblash qobiliyati
  

Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida amalga oshirish.
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini izlash. Ushbu umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu mavzu bilan bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday farq qiladi? Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini aniqlashga harakat qilamiz. Bizni samarali algoritmlarni loyihalashning asosiy usullarini minimal ma'lumot bilan namoyish etuvchi paradigmatik masalalar va usullar qiziqtiradi.
Algoritmni bajarilish qadami - bu ijrochi tomonidan bitta ko‘rsatmaning bajarilishidir. Bir masalani hal etuvchi ikkita algoritmdan kam qadam talab qilinayotgani samaraliroqdir. Samaradorlik o‘lchovi - bu bor-yo‘g‘i qadamlar sonidir. Lekin chuqurroq e’tibor berib qarasak, bu ta’rifdagi mujmal tomonlarni aniqlaymiz. Ba’zan avval uchragan algoritmlardagidan ko‘ra vaziyat murakkabroq bo’ladi.
Algoritmlar murakkabligi bilan ham farqlanishi mumkin. Algoritmning murakkabligini uning matnidagi satrlar soni bilan o‘lchaymiz. Shu bilan birga quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga hisoblaymiz
TAKRORLANSIN MARTA TAMOM
Mana, masalan, quyidagi algoritmda:
1 ni qo‘sh
TAKRORLANSIN 6 MARTA 2 ga ko‘paytir
1 ni qo‘sh
TAMOM
1 ni qo‘sh
TAKRORLANSIN 6 MARTA
TAMOM
2 ga ko‘paytir
1 ni qo‘sh
faqat 4 ta satr bor. Bu uning murakkabligi 4 ekanligini bildiradi.
Shuni aytib o‘tish joizki, hozir biz ko’rgan algoritm murakkabligi va samaradorligi o‘zaro tengdir. Masalan, bo‘ri, echki va karamni daryodan o‘tkazish algoritmi ham 7 satrdan iborat ham u 7 qadamda bajariladi.
Bu yerda bizni kerakli vositamiz bor: bu TAKRORLANSIN - MARTA tuzilmasi. Shuning uchun oshiruvchi tomonidan 17 sonini hosil qilish algoritmi 3 satrdan iborat bo‘ladi (eslatma: tuzilma 1 ta satr deb hisoblanadi):