Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari



Download 171.49 Kb.
bet1/4
Sana22.03.2021
Hajmi171.49 Kb.
  1   2   3   4

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Algoritmlarni loyihalash”

fanidan

MUSTAQIL ISH
Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari.

Bajardi:CAL010-guruh talabasi

Abduvohidova Zilola

Qabul qildi: Yusupova Zaynab



Toshkent 2020

  1. Samaradorlik ko’rsatkichlari.

  2. Algoritmlarni murakkabligini aniqlash.

  3. 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):


Download 171.49 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
O’zbekiston respublikasi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
davlat pedagogika
nomidagi toshkent
guruh talabasi
pedagogika instituti
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
rivojlantirish vazirligi
samarqand davlat
navoiy nomidagi
haqida tushuncha
toshkent davlat
ta’limi vazirligi
nomidagi samarqand
vazirligi toshkent
Darsning maqsadi
Toshkent davlat
tashkil etish
kommunikatsiyalarini rivojlantirish
Alisher navoiy
Ўзбекистон республикаси
matematika fakulteti
bilan ishlash
pedagogika universiteti
Nizomiy nomidagi
fanining predmeti
sinflar uchun
o’rta ta’lim
maxsus ta'lim
таълим вазирлиги
vazirligi muhammad
fanlar fakulteti
ta'lim vazirligi
tibbiyot akademiyasi
Toshkent axborot
махсус таълим
haqida umumiy
umumiy o’rta
Referat mavzu
ishlab chiqarish
fizika matematika
pedagogika fakulteti
universiteti fizika
Navoiy davlat