Dasturiy injiniring

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

SAMARQAND FILIALI

«KOMPYUTER INJINIRINGI» FAKULTETI

“DASTURIY INJINIRING” KAFEDRASI

ALGORITMLARNI LOYIHALASH VA TAHLIL QILISH

FANIDAN
MUSTAQIL ISH №2
MAVZU: ALGORITMLARNI BAHOLASH KRITERIYALARI HAQIDA MA’LUMOT BERING


Qabul qildi: I.Boynazarov
Tayyorladi: M.A.Sulaymonov


SAMARQAND 2021

2 - labaratoriya mashg’uloti topshirig’i natijalari

Quyidagi nazariy savollarga javob bering

1. 
   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 f_A(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(n^c) – Polinominal;

  
  

• f(n)=O(cⁿ) – eksponensial;

  
  

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

  
  

b) 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.