1 мustaqil ta’lim ish hisoboti Fan “ Algoritmlarni loyihalash” Guruh di21 10 Talaba Mirqosimov Mirsaid

2. Eng yaxshi, o'rtacha va eng yomon holatlar

Mamalakatimizning futbol bo'yicha milliy terma jamoasi nufuzli musobaqalarda qatnashayotganda barcha ishqibozlardan deyarli bir hil gapni eshitasiz. "Eng kamida yarim finalga chiqishimiz kerak.", "Yo'q eng zo'r holatda guruhdan chiqa olamiz, undan ortig'iga kuchimiz yetmaydi.", yoki eng yomon ko'rganimiz - "Eng kamida 6 ta to'p farqi bilan g'alaba qozonishimiz shu bilan birga Korea Eronni yutishi kerak.". Bularni algoritmlarga nima aloqasi bor? Demak algoritmlar haqida so'z yuritishni davom etarkanmiz, e'tiborimizni keyingi muhim xususiyat- algoritmning ishlash holatlari ga qaratamiz. Berilgan massivning ichidan kerakli elementni topish muammosini eslaylik.
/* massivdan kerakli element joylashgan indeksni topish.*/
public int ChiziqliQidiruv(int[] a, int t)
{
for (int i = 0; i < a.Length; i++)
if (t == a[i])
return i;

return -1;
}
Biz qidirayotgan son massivning birinchi indeksida yotgan bo'lsin. Bu algoritmning eng yaxshi xolati deyiladi sababi, for atigi bir marta ishlaydi. Endi aksincha kerakli son massivning eng so'ngida yotgan bo'lsin. Bu algoritmning eng yomon holati deyiladi. Sabab esa, algoritm massivning xar bir elementini tekshirib chiqishga majburligidir. Agar ush dasturni bir necha marta va xar hil o'lchamdagi massivlar bilan qaytarsak for n/2 marta ishlaydi va bu algoritmning o'rta holati deyiladi.
- Xo'p algoritm taxlil qilayotganimizda, qaysi bir holatni e'tiborga olishimiz kerak?
Odatda eng yaxshi holat e'tiborga olinmaydi. Sababi bu holat juda kamdan kam uchraydi va algoritmning ishlash vaqtini hisoblayotganimizda juda ham optimistik holat hisoblanadi. (Xar holda termamiz xar doim ham 6 to'p farqi bilan yutavermaydi va Korea xam yengilmas jamoa emas.) Boshqacha qilib aytganda bu holat orqali algoritmning husisiyatini to'liq ifodalab bo'lmaydi. Boshqa tarafdan esa, saralash algoritmlaridan birida eng yaxshi holatning uchrash extimolligi juda yuqori, bu vaziyatda eng yaxshi holatni ham e'tiborga olishimiz kerak bo'ladi. Nasib qilsa keyin maqolalarimizdan biridi ushbu saralash algoritmga to'xtalib o'tamiz.
Eng yomon holat haqidachi? Analiz vaqtida algoritim eng kamida shu holat darajasida yaxshi bo'lishini oldindan bilasiz. Ya'ni algoritm bajarishi mumkin bo'lgan operatsiyalarni maksimum darajada bajaradi. Shu sababdan, algoritmning eng yomon holatini yaxshilash orqali algoritmning ishlash vaqtida o'sishga erishasiz. Algoritmlar analizida ko'pincha shu holat e'tiborga olinadi.
Lekin xar doim ham eng yomon holat yetarli bo'lavermaydi. Aytaylik aynan bir dasturni bir necha marta ishlatib xar safargi ishlatilish uchun qancha vaqt ketganini analiz qilmoqchi bo'lsak, eng yomon holat eng ma'quli emas.

3. Algoritmni baholash mezonlari

Og'irlikni o'lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi.
Logarifmik o'lchov mezoni (LCV) ma'lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi.
LCV vaqt murakkabligi l (O p ) qiymati bilan belgilanadi , bu erda O p - operandning qiymati.
LCV ning sig'im murakkabligi l (M) qiymati bilan belgilanadi , bu erda M - xotira xujayrasining kattaligi.