Министерство по развитию информационных технологий и коммуникаций республики узбекистан каршинский филиал ташкентского университета информационных технологий

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.