Mustaqil ish Mavzu: Algoritmlarni eng yomon va o‘rtacha holatlarda baholash

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 xattiharakatlar esa O (N * log (N)) bahosi bilan tavsiflanadi, bu ancha tezroq.


III.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.
IV.Foydalanilgan adabiyotlar.
Pro-prof.com
Habr.com
Studfile.net
ziyonet