Algoritmlarni loyihalash”

Rekursiv algoritmlarning hajmiy murakkabligi

Barcha rekursiv algoritmlar uchun hajm murakkabligi tushunchasi juda muhimdir. Har bir qo'ng'iroq paytida protsedura oz miqdorda xotirani talab qiladi, ammo rekursiv qo'ng'iroqlar paytida bu miqdor sezilarli darajada oshishi mumkin. Shuning uchun har doim kamida rekursiv protseduralarning hajmli murakkabligini yuzaki tahlil qilish kerak.

O'rta va eng yomon ish

Algoritmni buyurtma qilishning murakkabligini baholash algoritmlar murakkabligining yuqori chegarasidir. Agar dastur katta murakkablik darajasiga ega bo'lsa, bu algoritm haqiqatan ham uzoq davom etadi degani emas. Ba'zi bir ma'lumot to'plamlarida, algoritmni bajarilishi ularning murakkabligi asosida taxmin qilishdan ancha kam vaqt talab etadi. Masalan, A vektorda berilgan elementni qidiradigan kodni ko'rib

chiqing. Agar kerakli element ro'yxatning oxirida bo'lsa, unda dastur N bosqichni bajarishi kerak bo'ladi. Bunday holda, algoritmning murakkabligi O (N) dir. Ushbu eng yomon holatda, algoritmning ishlash vaqti maksimal bo'ladi. Boshqa tomondan, kerakli narsa birinchi holatda ro'yxatda bo'lishi mumkin. Algoritm faqat bitta qadamni bajarishi kerak. Bunday holat eng yaxshi deb nomlanadi va uning murakkabligi O (1) deb baholanishi mumkin.

function Locate(data: integer): integer; var

i: integer;

fl: boolean; begin fl:=false; i:=1;

while (not fl) and (i<=N) do begin

if A[i]=data then fl:=true

else i:=i+1;

end;

if not fl then i:=0;

Locate:=I; end;

Ushbu ikkala holat ham mumkin emas. Bizni kutilgan variant ko'proq qiziqtiradi. Agar ro'yxat elementi dastlab tasodifiy aralashtirilsa, unda kerakli element ro'yxatning istalgan joyida paydo bo'lishi mumkin. O'rtacha, kerakli elementni topish uchun N / 2 taqqoslash talab qilinadi. Shunday qilib, ushbu algoritmning murakkabligi o'rtacha O (N

/ 2) = O (N).

Bunday holda, o'rtacha va kutilgan murakkablik bir xil, ammo ko'plab algoritmlar uchun eng yomon holat kutilganidan juda farq qiladi. Masalan, eng yomon holatlarda tez tartiblash algoritmi O (N ^ 2) tartibining murakkabligiga ega, kutilayotgan xatti- harakatlar esa O (N * log (N)) bahosi bilan tavsiflanadi, bu ancha tezroq.

Xulosa

Men bu mustaqil ishni bajarish jarayonida bir nechta maqolalarni ko’rib chiqdim.Ularda keltirilgan malumotlarni o’rganib chiqdim va bu menga masalaga qanday yondashish kerak ekanligini o’rgandim. Asosan masalini yechish uchun ketgan vaqt va uning xotiradagi hajmi va murakkablik darajasini baholash hamda unga qaysi usul bilan yondashish kerak ekanligini ham tushundim. Asosan masalini tushunarliligi hamda soddaligiga etibor qaratish kerak ekanligini unga kiritayotgan qiymatlarimiz xotiradan qancha joy egallashishini ham etibor berish kerak ekan chunki bu dastur o’qish jaroyonida ishga tushurish uchun ancha vaqt talab qilar ekan.

Foydalanilgan adabiyotlar.
Pro prof.com Habr.com Studfile.net ziyonet