Algoritmlarni loyihalash”

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;

Agar Tez protseduraning ichki tsikllarida Slow protsedurasi chaqirilsa, protseduralarning murakkabligi ko'paytiriladi. Bunday holda, algoritmning murakkabligi O (N ^ 2) * O (N ^ 3) = O (N ^ 5) dir.

Agar asosiy dastur protseduralarni navbat bilan chaqirsa, unda ularning qiyinchiliklari kuchayadi: O (N ^ 2) + O (N ^ 3) = O (N ^ 3). Quyidagi parcha xuddi shunday murakkablikka ega:

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

{какое-то действие} end;

procedure Both; begin Fast; Slow;

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.