Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar



Download 30,55 Kb.
bet1/8
Sana31.01.2021
Hajmi30,55 Kb.
#58040
  1   2   3   4   5   6   7   8
Bog'liq
Laboratoriya 1 - AL
Laboratoriya 1 - AL, УЗЕЛ СВЯЗИ Министерство обороны Российской Федерации, УЗЕЛ СВЯЗИ Министерство обороны Российской Федерации, topshiriq 8(2), O‘zbekistonda va chet mamlakatlarda elementar matematik tasavvurlarni shakllantirish metodikasi asoslarining rivojlanishi, 1-topshiriq, 16366062544245126 (1), 16366062544245126 (1), 16366062544245126, 16366062544245126, 16366062544245126, Лойиҳа матни - 201638-(212079), Лойиҳа матни - 201638-(212079)

Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar.

Ishdan maqsad: Talabalarda algoritmlarni asimptotik tahlil qilish haqida ko’nikmalar hosil qilish, masalalarni yechishda saralash, qidirish algoritmlarini qo’llash va ularni tahlil qilish orqali qulayini tanlash.

Nazariy qism:

Algoritmlarning asimptotik tahlili

Masalani yechish ko’pchilik hollarda ishlash prinspidan kelib chiqqan holda bir nechta algoritmlardan bittasini tanlashga to’g’ri keladi. Belgilangan qadamlardan keyin turli kiritiluvchi ma’lumotlarda ularning bari masalaning to’g’ri yechimiga olib boradi. Shunday bo’lsada mavjud variantlardan optimal metodni tanlashimiz lozim.

Optimallikning kriteriyasi bu algoritmning murakkabligidir. Odatda ikkita vaqt va hajm (egallangan joy) bo’yicha murakkablikka ajratishadi. Vaqt bo’yicha murakkablik berilgan masalani yechishda algoritm tomonidan amalga oshiriladigan elementar amal(instruksiya)larning soni bilan belgilanadi. Hajm bo’yicha murakkablik algoritm tomonidan foydalanilgan hotira hajmi bilan o’lchanadi. Endilikda biz faqat vaqt bo’yicha murakkablikni ko’rib chiqamiz.

Algoritmlarning ikki xil turi ajratib ko’rsatiladi, bular: takrorlanuvchi algoritmlar va rekursiv algoritmlar. Takrorlanuvchi algoritmlar asosida sikl va shart operatorlari yotadi. Bu sinf algoritmlarining analizi barcha sikllar va ular ichidagi amallar hisobini taqazo etadi. Rekursiv algoritmlar (rekursiv funksiya – o’z-o’zini chqiruvchi funksiya) esa asosiy masalani qismlarga ajratadi va ularning har birini alohida yechadi. Rekursiv algorutmlarning analizi anchayin murakkab. U masalani qismlarga bo’lish amallarini sonini, asosiy masalaning har bir qismida algoritmning bajarilishini, shu bilan birga ularning birlashmasini hisoblashni talab etadi.

Qaysi instruksiyalarni hisoblash kerak? Bu savolga aniq javob mavjud emas, lekin aniq faktki – hisoblashda mavjud operatsiyalar(amallar)ni inobatga olish lozim.

Ularga quyidagilarni kiritish mumkin:



  • Oddiy o’zlashtirish: а ← b ;

  • Massiv elementlarini indekslash (uning qiymatini aniqlash);

  • Arifmetik amallar: -, +, *, / ;

  • Solishtirish amallari: <, >, =, <=, >=, <> ;

  • Mantiqiy amallar: or, and, not.

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:



  • Ω (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:


Download 30,55 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8




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

    Bosh sahifa
davlat universiteti
axborot texnologiyalari
ta’lim vazirligi
zbekiston respublikasi
maxsus ta’lim
O’zbekiston respublikasi
nomidagi toshkent
guruh talabasi
o’rta maxsus
toshkent axborot
texnologiyalari universiteti
xorazmiy nomidagi
davlat pedagogika
rivojlantirish vazirligi
pedagogika instituti
vazirligi muhammad
haqida tushuncha
kommunikatsiyalarini rivojlantirish
respublikasi axborot
toshkent davlat
tashkil etish
vazirligi toshkent
Toshkent davlat
bilan ishlash
O'zbekiston respublikasi
matematika fakulteti
Ishdan maqsad
o’rta ta’lim
ta’limi vazirligi
fanining predmeti
saqlash vazirligi
moliya instituti
haqida umumiy
pedagogika universiteti
fanlar fakulteti
fanidan tayyorlagan
umumiy o’rta
samarqand davlat
ishlab chiqarish
fanidan mustaqil
Toshkent axborot
universiteti fizika
fizika matematika
uzbekistan coronavirus
Darsning maqsadi
sinflar uchun
Buxoro davlat
coronavirus covid
Samarqand davlat
koronavirus covid
sog'liqni saqlash