Algoritmlar samaradorligin baholash. Xotiraviy samara vaqt samarasi. Algoritmlarning murakkablik darajasi

Ma’ruza-2: Algoritmlar samaradorligin baholash.
Xotiraviy samara vaqt samarasi.Algoritmlarning murakkablik darajasi

Reja:

1. 
   Xotiraviy samara vaqt samarasi.
   
2. 
   Algoritmlarni tasvirlash usullari.
   
3. 
   Algoritmlarga doir misollar.
   

Tayanch iboralar: Аniqlik, Diskrеtlik, Оmmаviylik, Tushunаrlilik, Nаtijаviylik, Blоk-sхеmа, Аlgоritmik nоtаtsiya

1. 
   Algoritm va uning asosiy hossalari
   

Biz turli algoritmlarning samaradorligini muhokama qilib o ‘tdik. Algoritmning bajarilish qadami — bu Ijrochi tomonidan bitta ko‘rsatmaning bajarilishidir. Bir masalani hal etuvchi ikkita algoritm dan kam qadam talab qilinayotgani samaraliroqdir. Samaradorlik o ‘lchovi - bu bor-yo‘g‘i qadamlar sonidir.Lekin chuqurroq e ’tibor be rib qarasak, bu ta ’rifdagi mujmal tomonlarni aniqlaym iz. Ba’zan avval uchragan algoritmlardagidan ko‘ra vaziyat murakkabroq bo‘ladi. Hozircha bu masalaga chuqurlashib o‘tirmaymiz va chuqurroq bilim to ‘plam aguncha uning muhokamasini keyinga qoldiramiz. Algoritmlar murakkabligi bilan ham farqlanishi m um kin. Algoritm ning murakkabligini uning matnidagi satrlar soni bilan o ‘lchaymiz.
Shu bilan birga quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga hisoblaymiz: Algoritmning tavsifida «biror maqsadga erishishga qara- tilgan» jumlasi qo‘llanilgan. Bu maqsadni yuqorida keltirilgan misollarda ko‘rishimiz mumkin: ko‘chadan o‘tish, g‘ishtlar sonini hisoblash, yig‘indini hisoblash. Bular algoritmning natijaviylik (cheklilik) xossasi bilan bog‘liq. Bu xossaning mazmuni shundan iboratki, har qanday algoritm ijrochi chekli qadamdan so‘ng oxir-oqibat ma’lum bir yechimga olib kelishi kerak. Shuni ta‘kidlash joizki, algoritm avvaldan ko‘zlangan maqsadga erishishga olib kelmasligi ham mumkin. Bunga ba‘zan algoritmning noto‘g‘ri tuzilgani yoki boshqa xatolik sabab bo‘lishi mumkin. Ikkinchi tomondan, qo‘yilgan masala ijobiy yechimga ega bo‘lmasligi ham mumkin. Lekin salbiy natija ham natija deb qabul qilinadi.
1.4-misol
x²+x+1 = 0 kvadrat tenglama yechilsin.
Bu tenglamaga quyida keltirilgan «ax²+bx+c = 0 (a 0) ko‘rinishidagi kvadrat tenglamani yechish» algoritmini qo‘llab, teng­lama yechimga ega emasligini aniqlaymiz.

1. 
   Bu ham natija ekanligi sizga ma’lum diskriminant: D = b²—4ac hisoblansin;
   
2. 
   agar D < 0 bo‘lsa, tenglama yechimga ega emas deb olinsin va 5-bandga o‘tilsin;
   
3. 
   agar D = 0 bo‘lsa, yagona yechim ga teng deb olinsin va 5-bandga o‘tilsin;
   
4. 
   birinchi yechim ga, ikkinchi yechim ga
   

teng deb olinsin;

5. 
   tugallansin.