Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari univesiteti


Download 252.96 Kb.
Pdf ko'rish
Sana24.05.2020
Hajmi252.96 Kb.

O‘ZBEKISTON RESPUBLIKASI AXBOROT 

TEXNOLOGIYALARI 

VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH 

VAZIRLIGI 

MUHAMMAD AL-XORAZMIY NOMIDAGI 

TOSHKENT AXBOROT TEXNOLOGIYALARI 

UNIVESITETI 

 

 



 

 

Algoritmlarni loyihalash  fanidan 

 

 

 



 

 

Mustaqil Ishi 

 

 

Mavzu: Murakkablikning statik va dinamik o’lchovlari. 



Vaqt bo’yicha va hajmiy qiyinchiliklar. 

 

 



 

 

 



 

CAL006 - guruh talabasi 

Bajardi: Zokirov Shohnurjon 

 

 

 


Algoritm murakkabligini baholash. Xotira yoki vaqt. 

 

Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif 

qiladi. Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik 

xotira hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng 

qisqa masofani topish masalasi bo’la oladi. Bunda siz o’zaro bog’liq bo’lgan 

shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa masofani topishingiz 

kerak bo’ladi. Bunda biz barcha nuqtalar orasidagi qisqa masofalarni aniqlab 

ularni jadval shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofani 

aniqlashimizga 

to’g’ri kelganda shunchaki jadvaldan ma’lumotni olib 

qo’yishimiz mumkin bo’ladi. 

Natijani shu zahoti olishimiz mumkin, ammo bu juda katta hajm talab 

qiladi. Masalan biror katta xaritada 10 minglab nuqtalar bo’lishi mumkin va 

bizning jadvalimiz buning uchun 

10 milliarddan ortiq ma’lumotni saqlashiga 

to’g’ri keladi va bu taxminan 10GB ga yaqin xotirani band etishi mumkin. 

Ushbu holatdan hajm-vaqt murakkabligi kelib chiqadi. Shunda algoritm 

vaqt bo’yicha ishlash tezligi yoki hajm bo’yicha ishlash tezligi bilan baholanadi. 

Biz asosiy e’tiborni vaqt bo’yicha murakkablikka qaratamiz lekin shu 

bilan birga foydalaniladigan xotira hajmini ham aniq belgilashimizga to’g’ri 

keladi. 

 

Ketma-ketlikni baholash. 

Biz algoritmlarni o’zaro baholashimizda ularga kiruvchi ma’lumotni ham 

e’tiborga olishimizga to’g’ri keladi. Chunki ayni bir saralash algoritmi uchun 

1000 ta kiruvchi elementni saralash 1s, 100 000 element uchun esa 4-5 

soniya ketadigan bo’lsa, boshqa bir algoritm uchun esa bor-yo’g’i 2 s ketishi 

mumkin. Bunday sharoitda qaysi algoritm yaxshi ekanini aytish mushkuldir. 

Umumiy holatda esa algoritmni murakkabligini ayni bir kattalik bilan 

baholash mumkin bo’ladi. Buni quyidagicha tushunish mumkin: agar 

algori


tmga kiruvchi N ma’lumotlar oshganida algoritmning bajarilish vaqti f(N) 

funksiya bilan bir xilda ortsa algoritm O(f(N)) murakkablikka ega deyiladi. 

Keling, yaxshisi A[NxN] matritsaning har bir qatoridagi maksimal 

elementni topishni ko’rib chiqamiz: 



 

 

 



Ushbu algoritmda i o’zgaruvchi 0 dan N-1 gacha o’zgarib kelyapti 

hamda uning har bir o’zgarishida j o’zgaruvchi ham shu oraliqda o’zgaryapti. 

Demak bunda jami N*N marta takrorlanish sodir bo’lyapti. Bundan esa f(N) = 

N*N ga teng bo’ladi va algoritmning murakkabligi O(N*N) ekanligini 

aniqlashimiz mumkin. 

Endi algoritmni murakkablik darajasini baholashni ko’rib chiqaylik. 

Bunda algoritmdagi eng tez o’suvchi qismdan foydalanish kerak bo’ladi. 

Tasavvur qiling algoritm N^3 + N murakkablikka ega bo’lsin. Bunda biz 

murakkablikni O(N^3) deb olishimiz yetarli bo’ladi. Chunki bu yerda tez 

o’suvchi qism bu N^3. Ya’ni +N ta qo’shimcha amalni hisoblashning hojati 

qolmaydi. Misol uchun N=100 bo’lsin, shunda jami 1000100 ta amal bajariladi 

va bu N^3 dan atigi 0.01% gagina farq qiladi. 

 

Murakkablikni baholash. 

Dasturdagi murakkab algoritmlar asosan funksiya va protseduralarda 

bo’ladi. Keling, buni ko’rish uchun Fast hamda Slow nomli funksiyalar yaratib 

olaylik va bu funksiyalarning turli xil ko’rinishdagi murakkabligini baholab 

ko’raylik. 


 

Demak ushbu kodni ko’rib chiqamiz. 

Slow funksiyasi O(N^3) murakkablikka ega bo’lib unda ichma ich 3 ta for 

sikli mavjud: N*N*N. Buni osonlik bilan ko’rish mumkin. 

Endi Fast funksiyasini ko’radigan bo’lsak unda ichma-ich 2 ta for sikli 

mavjud. Ammo ikkinchi siklda biz Slow funksiyasini chaqirganmiz. Bu esa 

algoritmning murakkabligini yanada oshiradi, ya’ni O(N^2) * O(N^3) = O(N^5). 

Both funksiyasida biz ikkala funksiyadan ham foydalandik. Bunda 

funksiyalar ketma-

ket qo’llangani sabab ular ichidan murakkabligi katta 

bo’lgan funksiya asosiy funksiyaning murakkabligi bo’ladi ya’ni O(N^2) + 

O(N^5) = O(N^5). Endi berilgan N=100 da algoritmning ishlash vaqtini 

ko’radigan bo’lsak u quyidagicha: 

 

Demak bu Both funksiyasi 570 soniyadan ko’proq vaqt ishladi. Boshqa 



xarakteristikadagi mashinada bu ko’p yoki kam bo’lishi mumkin. 

Xulosa qiladigan bo’lsak oddiy takrorlanish algoritmlarining murakkabligi 

undagi takrorlanishlarning soniga bog’liq bo’ladi va buni aniqlash ancha oson. 

 


Rekursiv algoritmlarni baholash 

Oddiy rekursiya. 

Rekursiv funksiyalar bu o’z-o’zini chaqiruvchi funksiyalardir. Rekursiv 

algoritmlarni baholash juda murakkabdir. Ularning murakkabligini baholash 

nafaqat ichki foydalanilgan funksiyalar, yana rekursiyaning takrorlanishiga 

ham bog’liq bo’ladi. Keling oddiy rekursiya misolida faktorialni hisoblash 

funksiyasini ko’raylik: 

 

Ushbu rekursiv funksiyada ortiqcha sikllar va ortiqcha funksiyalar 



mavjud emas shuning uchun bu funksiya faqat N marta takrorlanadi va uning 

murakkabligi O(N) ga te

ng bo’ladi. Ushbu dasturning ishlash vaqti 

quyidagicha: 

 

Bundan tashqari rekursiv funksiyalarda rekursiya chuqurligi ya’ni 



rekursiyaning qancha marotaba takrorlanishi muammosi mavjuddir. Bu esa 

mashinaning xotira bilan bog’liq muammolariga bog’liqdir. 



Xulosa 

Xulosa o’rnida aytadigan bo’lsak, algoritmlar asosan quyidagicha 

ko’rinishdagi murakkabliklarda bo’ladi va barcha algoritmlarni baholashimiz 

uchun mana shu murakkabliklar yetarli bo’ladi: 

1.  C yoki O(1) - 

algoritm o’zgarmas vaqtda bajariladi. 

2.  O(log(log(N))) 

3.  O(log(N)) 

4.  O(N^C) 0

5.  O(N) 

6.  O(N*log(N)) 

7.  O(N^C) C > 1 



8.  O(C^N) C > 1 

9.  O(N!) 

 

Agar biz ushbu murakkablikni aniqlaydigan bo’lsak: 



O(log(N) + N!) = O(N!). Bunda f(N) = N! funksiya f(N) = log(N) funksiyadan 

ko’ra tezroq o’suvchi. Shuning uchun algoritmning murakkabligini O(N!) deb 

olishimiz yetarli bo’ladi. Quyida murakkabliklarning turli kiruvchi 

ma’lumotlardagi bajarilish vaqti keltirilgan: 



 

 

Download 252.96 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling