|
Toshkent axborot texnologiyalri universiteti algoritmlarni loyihalash
|
| bet | 5/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 RQiyinchilikni aniqlash
Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq qilish protseduralari. Oldingi misolda butun algoritm ikki tsikl yordamida amalga oshirildi. Agar bitta protsedura boshqasini chaqirsa, u holda protseduraning murakkabligini batafsilroq baholash kerak. Agar unda muayyan miqdordagi ko'rsatmalar bajarilgan bo'lsa (masalan, bosib chiqarish), unda bu murakkablikni baholashga deyarli ta'sir qilmaydi. Agar O (N) bosqichlar chaqirilayotgan protsedurada bajarilsa, funktsiya algoritmni sezilarli darajada murakkablashtirishi mumkin. Agar protsedura ko'chadan ichkarisiga chaqirilsa, u holda ta'sir yanada katta bo'lishi mumkin. Misol tariqasida ikkita protsedurani ko'rib chiqing: O (N ^ 3) murakkabligi bilan sekin va O (N ^ 2) murakkabligi bilan.
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun zarur bo'lgan vaqt va talab qilinadigan xotira miqdori hisoblanadi. Shuningdek, topshiriqlar sinfi uchun murakkablikni tahlil qilganda ma'lum bir ma'lumotni - kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi . Shunday qilib, algoritmning murakkabligi kirish hajmining funktsiyasi degan xulosaga kelishimiz mumkin.
Algoritmni o'sish tartibi
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta kirish o'lchamiga ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy xatti-harakatlarini tavsiflaydi. Bundan kelib chiqadiki, vaqtning murakkabligini baholashda elementar operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning bosqichlarini ko'rib chiqish kifoya qiladi.
Algoritmning bosqichi bu ketma-ket joylashgan elementar operatsiyalar to'plami bo'lib, ularning bajarilish vaqti kirish hajmiga bog'liq emas, ya'ni u yuqorida qandaydir doimiy bilan chegaralangan.
Asimptotik baholash turlar
O - eng yomon holat
F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini n> 0 ko'rib chiqing . Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , n 0 > 0 , keyin 0 n 0 .
Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq qiymatidir. Agar f (n) algoritmning murakkabligi funktsiyasi bo'lsa, unda murakkablik tartibi f (n) - O (g (n)) deb belgilanadi.
Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar sinfini belgilaydi.
Θ - o'rtacha ish uchun ball
Ta'kidlash joizki, n> n 0 uchun f (n) funktsiya hamma joyda c 1 * g (n) va c 2 * g (n) orasida bo'ladi , bu erda c doimiy omil. Masalan, f (n) = n 2 + n bilan ; g (n) = n 2 .
|
| |
