Algoritmlarni loyihalash”

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.