Fan nomi: “ Algoritmlarni loyihalash ” O`qituvchi

---

 
 
 
Fan nomi:
“
Algoritmlarni loyihalash
” 
O`qituvchi: 
To’xtayeva M.SH 
Talaba:
Nabiyev Muhamddtohir
SAMARQAND-2023
 

---

Nazariy topshiriqlar:
 
2. Algoritmlarni eng yomon va o’rtacha holatlarda baholash 
3. Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va logarifmik 
solishtirma mezonlar. 
4. Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash 
 
JAVOBLAR: 
1. Algoritmga algoritm deyiladi doimiy vaqt(vaqt sifatida qayd etilgan O (1)) 
qiymat bo'lsa T(n) kirish hajmiga bog'liq bo'lmagan qiymat bilan cheklangan. 
Masalan, massivda bitta elementni olish doimiy vaqtni oladi, chunki uni topish 
uchun bitta buyruq bajariladi. Biroq, tartiblanmagan massivda minimal 
qiymatni topish doimiy vaqtdagi operatsiya emas, chunki biz massivning har bir 
elementini skanerlashimiz kerak. Shunday qilib, bu operatsiya chiziqli vaqtni 
oladi, O (n). Agar elementlarning soni oldindan ma'lum bo'lsa va o'zgarmasa, 
bunday algoritmni doimiy vaqt algoritmi deb atash mumkin. 
"Doimiy vaqt" nomiga qaramay, ish vaqti vazifa hajmidan mustaqil bo'lishi 
shart emas, lekin ish vaqtining yuqori chegarasi bo'lmasligi kerak. Masalan, 
"qiymatlarni almashish" vazifasi a va b, zarur bo'lsa, natijada biz olamiz a≤b", 
doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash vaqti 
tengsizlikning mavjudligiga bog'liq bo'lishi mumkin. a ≤ b yoki yo'q. Biroq, 
ma'lum bir doimiylik mavjud t, ular uchun vazifani bajarish vaqti har doim 
oshmaydi t. 
Quyida doimiy vaqtda ishlaydigan ba'zi kod misollari keltirilgan: 
Int indeksi = 5; int element = ro'yxat; agar(shart to'g'ri) keyinboshqa doimiy ish 
vaqti bilan ba'zi operatsiyalarni bajarish uchun i = 1 uchun 100 uchun j = 1 
uchun 200 doimiy ish vaqti bilan ba'zi operatsiyalarni bajaradi 
Agar T(n) bu O ( ba'zi doimiy qiymat), bu ga teng T(n) O (1) dir. 
1. Algoritm murakkabligini static va dinamik o’lchovlari.Vaqt va hajm bo’yicha 
qiyinchiliklar 

---

2. Ushbu algoritmda i o'zgaruvchisi 1 dan N.gacha o'zgaradi, i ning har bir 
o'zgarishi 
bilan birga
, j o'zgaruvchisi ham 1 dan N ga o'zgaradi. Tashqi 
aylanishning har bir N takrorlanishida ichki pastadir ham N marta bajariladi. 
Ichki pastadir takrorlanishlarining umumiy soni N * N dir. Bu O (N ^ 2) 
algoritmining murakkabligini aniqlaydi. Algoritmning murakkablik tartibini 
taxmin qilishda faqat eng tez o'sadigan qismdan foydalanish kerak. Vazifalar 
aylanishi N ^ 3 + N ifodasi bilan tasvirlangan deb taxmin qiling. Bunday holda, 
uning murakkabligi O ga teng bo'ladi (N ^ 3). Funktsiyaning tez o'sib boruvchi 
qismini ko'rib chiqish, algoritmning xatti-harakatlarini N.ning ortishi bilan 
baholashga imkon beradi. Masalan, N = 100 bilan N ^ 3 + N = 1000100 va N = 
1000000 o'rtasidagi farq atigi 100 ga teng, bu 0,01%. O ni hisoblashda, 
ifodalarda doimiy omillarga e'tibor bermaslik mumkin. 3N ^ 3 ish bosqichiga 
ega bo'lgan algoritm O (N ^ 3) deb hisoblanadi. Bu O (N) nisbati muammoning 
hajmiga bog'liqligini yanada aniqroq qiladi. 
Qiyinchilikni aniqlash 
Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq qilish 
protseduralari. Oldingi misolda butun algoritm ikki tsikl yordamida amalga 
oshirildi. Agar bitta protsedura boshqasini chaqirsa, u holda protseduraning 
murakkabligini batafsilroq baholash kerak. Agar unda muayyan miqdordagi 
ko'rsatmalar bajarilgan bo'lsa (masalan, bosib chiqarish), unda bu 
murakkablikni baholashga deyarli ta'sir qilmaydi. Agar O (N) bosqichlar 
chaqirilayotgan protsedurada bajarilsa, funktsiya algoritmni sezilarli darajada 
murakkablashtirishi mumkin. Agar protsedura ko'chadan 
ichkarisiga chaqirilsa
, 
u holda ta'sir yanada katta bo'lishi mumkin. Misol tariqasida ikkita protsedurani 
ko'rib chiqing: O (N ^ 3) murakkabligi bilan sekin va O (N ^ 2) murakkabligi 
bilan. 
procedure Slow; 
var i,j,k: integer; 
begin 
for i:=1 to N do 
for j:=1 to N do 
for k:=1 to N do 
какое-то действие} 
end; 
procedure Fast; 
var 
i,j: integer; 
begin 
for i:=1 to N do 
for j:=1 to N do 

---

Slow; 
end; 
procedure Both; 
begin 
Fast; 
end; 
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun 
zarur bo'lgan vaqt va talab qilinadigan xotira miqdori hisoblanadi. Shuningdek, 
topshiriqlar sinfi uchun murakkablikni tahlil qilganda ma'lum bir ma'lumotni - 
kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi . Shunday qilib, 
algoritmning murakkabligi kirish hajmining funktsiyasi degan xulosaga 
kelishimiz mumkin. 
Algoritmning murakkabligi bir xil kirish hajmi bilan farq qilishi mumkin, 
ammo har xil kirish ma'lumotlari. Eng yomon , o'rta yoki eng yaxshi holatda 
murakkablik tushunchalari mavjud . Odatda, eng yomon ishning murakkabligi 
baholanadi. Vaqtning murakkabligi eng yomon holatda, berilgan o'lchamdagi 
masalani echishda algoritmni bajarish paytida bajariladigan operatsiyalarning 
maksimal soniga teng bo'lgan kirish hajmining funktsiyasi. Eng yomon holatda, 
kapasitiv murakkablik bu o'lchamdagi muammolarni echishda foydalanilgan 
xotira hujayralarining maksimal soniga teng kirish hajmi funktsiyasidir. 
Algoritmni o'sish 
tartibi
 
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta kirish 
o'lchamiga ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy 
xatti-harakatlarini tavsiflaydi. Bundan kelib chiqadiki, vaqtning murakkabligini 
baholashda elementar operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning 
bosqichlarini ko'rib chiqish kifoya qiladi. 
Algoritmning bosqichi bu ketma-ket joylashgan elementar operatsiyalar 
to'plami bo'lib, ularning bajarilish vaqti kirish hajmiga bog'liq emas, ya'ni u 
yuqorida qandaydir doimiy bilan chegaralangan. 
Asimptotik baholash turlar 
O - eng yomon holat 
F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini n> 
0 ko'rib chiqing . Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , 
n 0 > 0 , keyin 0 n 0 . 
Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq qiymatidir. 
Agar f (n) algoritmning murakkabligi funktsiyasi bo'lsa, unda murakkablik 
tartibi f (n) - O (g (n)) deb belgilanadi. 
Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar sinfini 
belgilaydi. 

---