Dasturiyinjiniring

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

SAMARQAND FILIALI

“DASTURIYINJINIRING”

Kafedrasi

“Algoritmlarni loyihalash va tahlil qilish”

MUSTAQIL ISH №2

fanidan

Mavzu: ALGORITMLARNI LOYIHALASH FANIGA KIRISH

Tayyorladi: Shirinov V.

Qabul qildi: Boynazarov I.

Savol: Algoritmlarni baholash kriteriyalari haqida ma’lumot bering

Algoritmni tahlil qilishda quyidagi usullar mavjud:

1.Algoritmlarning eksperimental (empirik) taqqoslash - dasturni ishlatish jarayonida vaqt (xotira) buyicha taqqoslash

2.Algoritmlarning asimptotik taxlili - turli faktorlarga bogliq holda vaqt (xotira) ni nazariy baxolash.

Agar fA(n)  o’sish tartibi n dan bog’liq bo’lgan polinomdan katta bo’lmasa, A algoritm polinomial deb aytiladi, aks holda algoritm A eksponensial hisoblanadi.

Bundan tashqari quyidagi baholashlar mavjud:

• f(n)=O(1) – o’zgarmas;

  
  

• f(n)=O(log n) – Logarifmik;

  
  

• f(n)=O(n) – Chiziqli;

  
  

• f(n)=O(nc) – Polinominal;

  
  

• f(n)=O(cn) – eksponensial;

  
  

• f(n)=O(n!) – faktorial.

  
  

Savol: Algoritmning bajarilish vaqtini baholang. Algoritmlarning turli holatlardagi samaradorligini tahlil qiling.

Bitta masalani hal qilish uchun turli xil algoritmlarni ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, biz hisoblashning qaysi turidan foydalanilganligi to'g'risida kelishib olishimiz kerak .. Algoritmning ishlash vaqti bilan biz bajaradigan elementar qadamlar sonini tushunamiz. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab qilinadi (masalan, ba'zi murakkab harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x-koordinata bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq qilish) protsedurasini (ma'lum miqdordagi operatsiyalarni oladi) va uning bajarilishini (bajarilishini) farqlashingiz kerak, ular uzoq davom etishi mumkin.

Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir.

Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n) murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda baholanadi. Baholashning eng oson usuli bu eksperimental usul, ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir qiladi:

Dastur algoritmining vaqt murakkabligi;

2. bajariladigan dasturning kompilyatsiya qilingan kodining sifati;

3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.

Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligini o'lchashning tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (har bir algoritmni kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va turli xil kompyuterlar.

Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.

Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.

Savol: Quyidagi masalalar uchun algoritm tuzing va uni tahlil qiling. Dastur kodini yozib natija oling.

1. 
   Stolda A1 × B1 × C1 o'lchamdagi quti va A2 × B2 × C2 o'lchamdagi quti joylashgan. Ushbu qutilardan birini ikkinchisining ichika kirishi mumkinligini aniqlash dasturini tuzing. Qutilarga ixtiyoriy tomonini 90 daraja aylantirishga ruxsat berilgan.