Algoritmlarni loyihalash

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI

VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKЕNT AXBOROT TЕXNOLOGIYALARI UNIVЕRSITЕTI

TELEKOMMUNIKATSIYA FAKULTETI

II BOSQICH TF-410-18-GURUH TALABASI

YUSUPOV BEKZODNING

“ALGORITMLARNI LOYIHALASH” FANIDAN TAYORLAGAN

2 - MUSTAQIL ISH

Guruh : CAL013

Bajardi: Yusupov Bekzod

Tekshirdi: Mustapakulov Yazdonqul.

Toshkent 2020

Masalaning nerilishi :

Ustuvor navbatda elementlar sonini topish va eng katta elementni yechib olish funksiyasi tuzilsin.

#include

#include

using namespace std;

void showpq(priority_queue gq)

{

priority_queue g = gq;

while (!g.empty())

{

cout << '\t' << g.top();

g.pop();

}

cout << '\n';

}

int main ()

{

priority_queue gquiz;

gquiz.push(10);

gquiz.push(30);

gquiz.push(20);

gquiz.push(5);

gquiz.push(1);

cout << "Ustuvor navbat elementlari : ";

showpq(gquiz);

cout << "\nelementlar soni : " << gquiz.size();

cout << "\nMax element : " << gquiz.top();

cout << "\nQolgan elementlar : ";

gquiz.pop();

showpq(gquiz);

return 0;

}



Nazorat savollari:

1. 
   Nima sababdan algoritmlarning samaradorligini baholash amalga oshiriladi?
   
2. 
   Vaqt bo’yicha murakkablikda yaxshi va yomon holatlar bir xil bo’lishi mumkinmi? Xulosangizni misollar orqali tushuntiring.
   
3. 
   Rekursiv algoritmlarning murakabligini baholashning asosi nimada?
   

Javoblar:

1.Masalani yechishda ko’pchilik hollarda ishlash prinspidan kelib chiqqan holda bir nechta algoritmlardan bittasini tanlashga to’g’ri kelganligi hamda belgilangan qadamlardan keyin turli kiritiluvchi ma’lumotlarda ularning bari masalaning to’g’ri yechimiga olib borishligi uchun Algoritimlarning samaradorligini baholash lozim .

. U masalani qismlarga bo’lish amallarini sonini, asosiy masalaning har bir qismida algoritmning bajarilishini, shu bilan birga ularning birlashmasini hisoblashni talab etadi.

2.Algoritmning vaqt bo’yicha murakkabligiga kirish ma’lumotlarining hajmi sezilarli ta’sir ko’rsatadi. Unchalik kata bo’lmagan hajmdagi ma’lumotlarni qayta ishlashda ikkita turli algoritmning ishlash vaqti ahamiyatsizdek tuyulishi mumkin, ammo ma’lumotlar hajmining ortishi ularning bajarilish vaqtiga sezilarli darajada ta’sir ko’rsatishi mumkin.

Lekin vaqt bo’yicha murakkablik faqatgina hajmga emas, balki ma’lumotlarning qiymatiga, shuningdek ularning tushish(uchrash) tartibiga ham bog’liq. Masalan, ko’pchilik saralash algoritmlari agar massivning o’zi saralangan bo’lsa, massivni tartiblashga anchayin kam vaqt sarflaydi. Shu kabi holatlar sabab vaqt bo’yicha murakkablikni uch xil holatda ko’rib chiqiladi: yomon, yaxshi va o’rta.

Yomon holat kirish ma’lumotlarining omadsiz kiritilishida ya’ni algoritm masalani yechish uchun maksimal sondagi elementar amallarni bajarishi to’g’ri kelish holatiga mos keladi. Yaxshi holatda aksincha kirish ma’lumotlari imkon qadar minimal sondagi amallarni bajarilishi ta’minlaydi.

O’rta holat anchayin murakkab aniqlanadi. Kirish ma’lumotlari imkon darajasida guruhlarga ajratiladi. Keyin har bir guruhning qatnashish ehtimolligi aniqlanadi. Shundan so’ng, har bir guruhning ma’lumotlar bilan ishlashi bo’yicha algoritmning ishlash vaqti hisoblanadi. Bizni ko’pincha eng kam va eng ko’p holatlari ko’proq qiziqtiradi.

Kiritiluvchi ma’lumotlarning hajmi katta bo’lganda biror masalaning ekzemplyar(nusxa) asosida bajariluvchi yechimi, algoritmlarning ishlash vaqti analizini solishtirish asimptotik tahlil deb yuritiladi. Asimptotik murakkabligi kamroq bo'lgan algoritm ko'proq samarador (effektiv) hisoblanadi.

Asimptotik tahlilda algoritmning murakkabligi – bu algoritmning ma’lumotlari hajmi ortishi bilan algoritmning ishlash vaqtining tezkor ravishta ortishini belgilovchi funksiyadir. Asimptotik tahlilda asosiy uchraydigan o'sishni baholash funksiyalari bular:

• 
  (O-katta) – vaqtni o'sishini yuqori asimptotik baholash funksiyasi;
  

• 
  Ω (Omega) – vaqtni o'sishini quyi asimptotik baholash funksiyasi;
  
• 
  Θ (Teta) - vaqtni o'sishini quyi vayuqori asimptotik baholash funksiyasi.
  

Bunda n – ma'lumotlarning hajmiy kattaligi bo'lsin. U holda f(n) algoritmning o’sish funksiyasini asimptotik jihatdan g(n) funksiya bilan chegaralash mumkin:

Mazmuni	Tavsifi
f(n) ∈ Ο(g(n))	f yuqoridan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan
f(n) ∈ Ω(g(n))	f quyidan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan
f(n) ∈ Θ(g(n))	f yuqori va quyidan g funksiya bilan chegaralangan

Misol uchun, muassasaning tozalash vaqti uning maydoni kattaligiga chiziqli ravishta bog’liq (Θ(S)), ya’ni maydon kattaligining n marta ortishi bilan uni tozalash vaqti ham n marta ortadi. Telefon daftarchasidan ismni qidirishda agar chiziqli qidirish algoritmidan foydalanilsa, O(n) chiziqli vaqtni talab etadi. Agar ikkilik qidiruvdan foydalanilsa, u holda (Ο(log₂(n))) yozuvlar soniga logarifmik bog’liq bo’ladi.

Biz O – funksiya bilan ko’proq kuzatuvlar olib boramiz. Keyingi kuzatishlarda algoritmlarning murakkabligi yuqori asimptotik chegara bilan beriladi.

3.Quyida eng ko’p uchraydigan murakkablik sinflari keltirilgan:

• 
  O(1) – konstantali murakkablik;
  
• 
  О(n) – chiziqli murakkablik;
  
• 
  О(n^а) – polynomial murakkablik;
  
• 
  О(log(n)) – logarifmik murakkablik;
  
• 
  O(n*log(n)) – kvazichiziqli murakkablik;
  
• 
  O(2ⁿ) – eksponensial murakkablik;
  
• 
  O(n!) –factorial murakkablik.
  

Xulosa :

Men bu labaratorya ishida Ustuvor navbat elementlari sonini toppish hamda eng katta elementni yechib olish funksiyalarini ishlatdim va o`rgandim.