2-мustaqilta’limishhisoboti Fan- “Algoritmlarniloyihalash” Bajardi: Ergasheva Sevara Tekshirdi: Bobonazarov Akmal

Algoritm murakkabligi static va dinamik o'lchovlari bilan baholash mumkin.


Statik murakkablik, algoritmlarning bajarish uchun kerak bo'lgan maksimal ishga tushirish resurslari soni, ya'ni bajariladigan operatsiyalar soni bilan belgilanadi. Algoritming ish tartibi o'zgartirilgan holda ham resurslar soni o'zgarmaydi. Statik murakkablik O(n) va boshqa murakkabliklar jihatidan yuzaga keladi.


Dinamik murakkablik esa ikkinchi birga ko'pincha qo'llaniladigan baholash usuli hisoblanadi. Bu usulda murakkablik, bajarilgan amallar soni, tashkil etiladigan obyektlar yoki o'lchashga qo'yilgan boshqa belgilashlar yordamida aniqlanadi. Dinamik murakkablikcha O(1), O(log n), O(n) va boshqa murakkabliklar jihatidan belgilanishi mumkin. Dinamik murakkablik, bir necha kerakli sahifalardan tashkil topgan web-saytlarini va qo'shimcha jadvallarni tuzishda qo'llaniladi.


O(n) va O(n^2) murakkablikdagi algoritmlar vaqt va hajm bo’yicha qiyinchiliklar bilan bog'liq bo'ladi.


O(n) murakkablikdagi algoritm bizga n ta elementni qidirish yoki saralash vaqtini beradi. Bu demak, algoritmning ishga tushirish vaqtida n elementni qidirish yoki saralashdir va ishga tushirish shunchaki n ta bog'liq operatsiyalar almashishi kerak.


O(n^2) murakkablikdagi algoritm davlatlar matritsa mavjud bo'lganda, matritsaning ichidagi yagona element bilan ishlovchi algoritmni taqdim etadi. Bu demak, algoritmning ishga tushirish vaqtida, u davlatlar matritisidagi elementlar soniga n^2 ga teng bo'lgan ta bog'liq operatsiyalar almashishi kerak.


Bunday murakkablikdagi algoritmlar tijoratda va boshqa sohalarda juda qiyin hisoblanadi, chunki ularning ishga tushirish vaqtida shunchaki ko'p vaqt sarflash kerak bo'lgan bog'liq operatsiyalar bor. Shunga qaramay, murakkablikning kichikroq darajadagi algoritmlar hech qachon murakkab bo'lmaydi va ularning ishga tushirish vaqtida kamida bog'liq operatsiyalar almashishi kerak.


Algoritmlarni en yomon va ortacha holatlarda baholash esa murakkablikni yoki ustuvorlikni tushunish uchun muhimdir. Bu, algoritmlarni to’g’ri narxlarda va yomon holatlarda ishlash va mijozlarga qilingan qiziqishni ko’rsatish uchun juda kerakli. Algoritmlarni en yomon holatlarda baholash uchun qo'shimcha test kengaytmasi kamida bir nechta kundan.o'tkaziladi. Va ortacha holatlarda baholash uchun esa ko'p marta bajariladigan baholash huquqi ishlatiladi.