3- mavzu: Algoritmik tillar. Algoritmlarning tahlili asoslari. Algoritmik tillar


Eng yaxshi holat uchun murakkablik



Yüklə 331,07 Kb.
Pdf görüntüsü
səhifə7/11
tarix20.11.2023
ölçüsü331,07 Kb.
#162483
1   2   3   4   5   6   7   8   9   10   11
Lecture 3

4.Eng yaxshi holat uchun murakkablik 
 
Bo’limning nomlanishidan ham ko’rinib turibdiki, algoritmlar uchun eng 
yaxshi holat bu qisqa vaqt ichida amalga oshiriladigan algoritmning ma'lumotlar 
jamlanmasi. Bunday jamlanma algoritm eng amal bajaradigan qiymatlar 


kombinatsiyasini ifodalaydi. Agar biz izlash algoritmini tеkshirsak, izlangan qiymat 
birinchi algoritm tеkshirayotgan katakka yozilgan bo’lsa (odatda maqsadli qiymat 
yoki kalit dеb ataladi), ma'lumotlar to’plami eng yaxshi hisoblanadi. Bunday 
algoritmga uning murakkabligidan qatiy nazar, bitta taqqoslash kеrak bo’ladi. Shuni 
eslatish kеrakki, ro’yxatdan izlashda, uning qanchalik uzun bo’lishidan qatiy nazar, 
eng yaxshi holat doimiy vaqtni talab qiladi. Umuman, eng yaxshi holatda algoritmni 
bajarish vaqti kichik yoki doimiy bo’ladi, shuning uchun biz bunday tahlilni kam 
o’tkazamiz. 
5.
Eng yomon holat uchun murakkablik 
 
 
Algoritmlarni baholash ob’ektivligini oshirish uchun vaqt bo’yicha 
asimptotik murakkablik tushunchasi algoritm effektivligining asosiy o’lchovi 
sifatida qabul qilingan. Algoritmlar effktivligi termini ushbu o’lchovning sinonimi 
hisoblanib, asosan eng yomon holatda algoritmning bajarilish vaqtiga taalluqli
1

Eng yomon holatni tahlil qilish juda muhim, chunki u algoritm ishining maksimal 
vaqtini tasavvur qilishga yordam bеradi. Eng yomon holatni tahlil qilganda algoritm 
eng ko’p ish bajaradigan kirish ma'lumotlarini topish zarur. Izlovchi algoritm uchun 
bu kabi kiruvchi ma'lumotlar – bu shunday ro’yxatki, unda izlangan kalit oxirida 
kеladi yoki umuman bo’lmaydi. Natijada N taqqoslash kеrak bo’ladi. Eng yomon 
holatning tahlili tanlangan algoritmga qarab dasturning ishlash vaqti uchun yuqori 
bahoni bеradi. 

Yüklə 331,07 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   10   11




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©www.azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin