O`zbekiston respublikasi axborot texnologiyalar va kommunikatsiyalarni rivojlantirish vazirligi muhammad

Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti. 
Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha 
hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng 
samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan 
foydalanilganligi to'g'risida kelishib olishimiz kerak. Ushbu ta'lim, bir model 
sifatida, eng qismi uchun, biz oddiy bir protsessor foydalanish tasodifiy kirish 
mashinasi ( tasodifiy - kirish mashinasi , RAM operatsiyalar parallel ijro uchun 
taqdim emas). Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar 
qadamlar sonini anglatadi. Aytaylik, psevdokodning bir qatorida belgilangan 
miqdordagi operatsiyalar talab etiladi (agar ba'zi bir xatti-harakatlarning og'zaki 
tavsifi bo'lmasa - masalan, "hamma nuqtalarni x- koordinata bo'yicha saralash "). 
Qo'ng'iroq qilish ( qo'ng'iroq qilish ) protsedurasini (ma'lum miqdordagi 
operatsiyalarni o'z ichiga olgan) va uning bajarilishini ( bajarilishini ) uzoq vaqt 
davomida ajratib turishingiz kerak . 
Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan 
manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan 
qiymatdir. Shunday qilib, biz algoritmning vaqtinchalik T ( n ) va fazoviy V ( n ) 
murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz 
vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga 
o'xshash tarzda baholanadi. Baholashning eng oson usuli - bu eksperimental, ya'ni 
algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha 
bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator 
kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat 

---

jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga 
quyidagi omillar ta'sir qiladi: 
1. Dastur algoritmining vaqt murakkabligi;
2. Bajariladigan dasturning kompilyatsiya qilingan kodining sifati;
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari. 
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligi 
tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va 
boshqalar), chunki agar siz turli xil dasturchilar (algoritmni kim dasturlasa) bir xil 
algoritm uchun har xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va 
turli xil kompyuterlar. Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga 
bog'liq. Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n 
hajmi kirish ma'lumotlari asosida) n . Amaliyotda T ( n ) ning aniq qiymatini 
aniqlash juda qiyin. Shuning uchun asimptotik munosabatlarga murojaat qiling
O- harflar. 
Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy 
jihatdan hisoblaydigan usul mavjud. 
Insertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun 
biz uning narxini (operatsiyalar sonini) va ushbu satr har bir satrning yonida necha 
marta bajarilishini belgilaymiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = 
uzunlik [ A ] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, 
bu sonni t j bilan belgilaymiz . Davr ichidagi chiziqlar tekshiruvdan bir marta kam 

---

bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Satr qiymati c takrorlangan 
t marta hissa beradi c  m operatsiyalar umumiy sonida (ammo, bu ibora ishlatilgan 
xotira hajmini hisoblash uchun ishlatilishi mumkin emas). Barcha qatorlarning 
hissalarini qo'shsak, olamiz 
Jarayonning ishlash vaqti nafaqat n ga bog'liq , balki kirishning kirish 
qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq . 
Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng 
maqbul holat. So'ngra line davr birinchi tekshirish keyin 5 tugaydi (buyon A [ i ] ≤ 
asosiy uchun i = j - 1), shuning uchun hamma narsani t j umumiy vaqti 1, va 
Shunday qilib, eng qulay holatda, vaqt t ( n ), hajmi bir qator saralash uchun zarur 
n, bir chiziqli funksiya (bo'lgan chiziqli funktsiyasi ) tomonidan n , masalan a va b 
ba'zi turg'unliklar uchun T ( n ) = a  n + b shakli mavjud . Ushbu Sobit tanlangan 
qiymatlari orqali aniqlanadi bilan 1 , ... , bilan 8 . Agar qator teskari (pasayish) 
tartibda joylashgan bo'lsa, ish vaqti protsedura maksimal bo'ladi: A [ j ] har bir 
elementni A [1] , ..., A [ j - 1] barcha elementlar bilan taqqoslash kerak . Bundan 
tashqari, t j = j . Chunki 
biz eng yomon holatda protsedura vaqti ekanligini tushunamiz. 

---

Bunday holda, T ( n ) - kvadrat ( kvadratik funktsiya ), ya'ni. shakli mavjud T ( n ) 
= a  n 2 + b  n + s . A , b va c konstantalari bu erda c 1 , ..., c 8 qiymatlari bilan 
ham belgilanadi . 
Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n hajmi kirish 
ma'lumotlarining) n . Amaliyotda T ( n ) ning aniq qiymatini aniqlash juda qiyin. 
Shuning uchun, ular yordamida asimptotik munosabatlar murojaat O -symbolics. 
Masalan, agar algoritm ishlashi uchun talab qilinadigan tadbirlar (harakatlar) soni 
16 n 2 + 12 n  log n + 2 n + 3 bilan ifodalangan bo'lsa , u holda algoritm T ( n ) 
ning O ( n 2 ) tartibida bo'lishini anglatadi. ) Asimptotik Omatikani 
shakllantirishda , barcha asl ifoda shartlari katta n uchun eng katta hissa 
qo'shadigan narsa bilan qoldiriladi (qolgan atamalar e'tiborsiz qoldirilishi mumkin) 
va uning oldidagi koeffitsient e'tiborga olinmaydi (chunki barcha asimptotik 
baholar doimiygacha berilgan). Belgilangan O () ishlatilganda, ular aniq bajarilish 
vaqtini anglatmaydi, balki faqat uning yuqori chegarasi, doimiy omilgacha. 
Masalan, algoritm O ( n 2 ) tartibining vaqtini talab qiladi deb aytganda , ular 
vazifaning bajarilish vaqti elementlar sonining kvadratidan tezroq o'smasligini 
anglatadi.