Norqulova dilfuzaning algoritimlarni loyhalash

3. Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va 
o'rtacha ish vaqti.

Kirish. 
Har qanday dasturchi uchun algoritmlar nazariyasining asoslarini bilish juda 
muhim, chunki algoritmlarning umumiy xususiyatlarini va ularni namoyish 
etish uchun rasmiy modellarni o'rganadigan fan. Hatto informatika 
darslaridan bizga kelajakda maktabga qaraganda murakkabroq topshiriqlarni 
yozishda yordam beradigan oqim jadvallarini tuzishga o'rgatiladi. Hech 
kimga sir emaski, deyarli har doim ma'lum bir muammoni hal qilishning bir 
necha yo'li mavjud: kimdir ko'p vaqt sarflashni, boshqalari resurslarni 
sarflashni o'z ichiga oladi, boshqalari esa deyarli echim topishga yordam 
beradi.
Siz har doim vazifaga muvofiq, xususan, muammolar sinfini hal qilish 
algoritmlarini ishlab chiqishda eng maqbul variantni izlashingiz kerak. 
Shuningdek, algoritm turli xil hajmlar va miqdorlarning boshlang'ich 
qiymatlarida o'zini qanday tutishi, unga qanday resurslar kerakligi va 

---

yakuniy natijani olish uchun qancha vaqt kerakligini baholash ham 
muhimdir.
Algoritm tushunchasi va uning ta’rifi.
Ma'lumotni qayta ishlash algoritmi - bu kompyuter fanida muammoni hal 
qilish usulining tavsifi bo'lib, uni keyinchalik tanlangan dasturlash muhitida 
amalga oshirish mumkin.
Algoritmni tahlil qilish - bu baholashni o'rganadigan informatika 
sohasidirishlash algoritmlari .
Algoritmning murakkabligi bu algoritmni tahlil qilishda hisobga olinadigan 
elementar operatsiyalar sonidir.
A algoritmi bilan belgilangan operatsiyalarning eng ko'p soni og'irlikning 
eng yomon holati bo'lib , u ma'lum bir o'lchovdagi D kirishlarni kiritadi .
Laboriousness eng yaxshi ishi algoritm operatsiyalar kichik soni A barcha 
yozuvlari da bir D ma'lum o'lchov n .
Laboriousness o'rtacha ishi algoritm operatsiyalar o'rtacha soni A barcha 
yozuvlari da bir D ma'lum o'lchov n .
Algoritmning murakkabligi funktsiyasi - algoritmning murakkabligi bu D 
kirishidagi A parametr parametrlariga bog'liqligi .
Algoritmning vaqt murakkabligi eng yomon holatga algoritmning 
murakkablik funktsiyasini asimptotik baholashdir.
Xotira hajmi - D kirish uchun A algoritmini amalga oshirishda ishtirok 
etadigan xotira joylarining maksimal soni .
Algoritmning kapasitiv murakkabligi bu algoritmning eng yomon holatdagi 
xotira funktsiyasini asimptotik baholashdir.
Algoritmning eng yomon, o'rta va eng yaxshi holatlaridagi resurslarning 
murakkabligi 
vaqt 
va 
funktsiyalar 
sinflarining 
tartiblangan 
juftligi.asemptomatik belgi bilan aniqlanadigan va ko'rib chiqilayotgan 
holatga mos keladigan sig'im murakkabligi .
Ma'lumotlar tuzilmalari bilan ishlash algoritmlari bu olinadigan asosiy 
tamoyillar va metodologiyani aniqlaydigan algoritmlardirma'lumotlarni 
qayta ishlash usullarini tushunish .
Saralash algoritmlari massivlar va fayllarni tartibga solish uchun 
mo'ljallangan algoritmlardir.
Qidiruv algoritmlari bu katta ma'lumotlar to'plamida ma'lum elementlarni 
qidirish uchun mo'ljallangan algoritmlar.

---

.
Xotira yoki vaqt
Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. 
Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq 
hajmni olib, sekinroq hal qilish mumkin. Bu holatda odatiy misol eng qisqa 
yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini 
taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng 
qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Bu 
masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar orasidagi 
eng qisqa masofani ko'rsatib, natijalarni jadvalga saqlashimiz mumkin. 
Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lsa, 
biz shunchaki jadvalning tugagan masofasini olishimiz mumkin. Natija bir 
zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta 
shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida 
tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. Bular 
Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani 
ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib 
chiqadi. Ushbu yondashuv bilan, algoritm bajarilish tezligi va iste'mol 
qilinadigan xotira nuqtai nazaridan baholanadi. Vaqtinchalik murakkablikka 
e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning 
hajmini aniq belgilaymiz.
Buyurtmani baholash
Turli xil algoritmlarni taqqoslashda ularning murakkabligi kirish 
ma'lumotlari miqdoriga bog'liqligini bilish muhimdir. Masalan, bitta usul 
yordamida saralashda ming sonlarni qayta ishlash 1 s., Va million sonlarni 
qayta ishlash uchun 10 s vaqt kerak bo'ladi, boshqa algoritmdan foydalanish 
esa 2 s vaqtni talab qilishi mumkin. va 5 s. navbati bilan Bunday sharoitda 
qaysi algoritm yaxshiroq ekanligini aniq aytish mumkin emas. Umumiy 
holda, algoritmning murakkabligini kattalik tartibida baholash mumkin. 
Agar kirish ma'lumotlarining o'lchamlari oshgani sayin, algoritmning 
bajarilish vaqti f (N) funktsiyasi bilan bir xil tezlikda oshsa, algoritmda O (f 
(n)) murakkablik bor. A [NxN] matritsasi uchun har bir satrda maksimal 
elementni topadigan kodni ko'rib chiqing. for i:=1 to N do begin
max:=A[i,1]; for j:=1 to N do begin if A[i,j]>max then max:=A[i,j] end;
writeln(max);
end;

---

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;

---

Ta'kidlash joizki, n> n 0 uchun f (n) funktsiya hamma joyda c 1 * g 
(n) va c 2 * g (n) orasida bo'ladi , bu erda c doimiy omil. Masalan, f (n) = n 
2 + n bilan ; g (n) = n 2 .
Algoritmni baholash mezonlari