|
Toshkent axborot texnologiyalri universiteti algoritmlarni loyihalash
|
| bet | 2/6 | | Sana | 05.03.2024 | | Hajmi | 131.97 Kb. | | #167339 |
Bog'liq Axmedov A. Коррупция, React 50 вопросов на собеседование, Linkedin, Маърузалар матни, 1 ON savollari, irregular VERBS, 3.Pul oqimlari to’g’risidagi hisobot, Toshkent davlat iqtisodiyot universiteti, 7-Mavzu obligatsiyalar bozori reja, «tasdiqlangan», Дизайн без названия, 7-Mavzu obligatsiyalar bozori reja (1), WEB yakuniy pdflar (3), 4-amaliy ish mavzu Risklarni baholash usullari. Riskni “Nosozli, Topografik chizmachilik. Murodov Sh. Ismatullayev RO'rta va eng yomon ish
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.
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. Afsuski, o'rtacha holatni hisoblashni imkoni xar doim ham bo'lavermaydi. Keyingi maqolalardan birida bunga yana bir bor to'xtalib o'tishga harakat qilamiz.
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.
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.
|
| |
