Norqulova dilfuzaning algoritimlarni loyhalash
Download 1.19 Mb. Pdf ko'rish
|
Algoritim 1-MI
|
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. Umumiy qiyinchiliklarni baholash xususiyatlari Endi biz murakkablikni hisoblash uchun eng ko'p ishlatiladigan ba'zi funktsiyalarni sanab o'tamiz. Vazifalar murakkablikning ortib boradigan tartibida keltirilgan. Ushbu ro'yxatdagi funktsiya qanchalik yuqori bo'lsa, bunday taxminga ega algoritm tezroq bajariladi. 1. C doimiy 2. log (log (N)) 3. log (N) 4. N ^ C, 8. C ^ N, C> 1 9. N! Agar murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholashni istasak, tenglamani jadvalda joylashgan funktsiyaga kamaytirish mumkin. Masalan, O (log (N) + N!) = O (N!). Agar algoritm kam miqdordagi ma'lumotlarga kamdan-kam hollarda chaqirilsa, O (N ^ 2) murakkabligini maqbul deb hisoblash mumkin, ammo agar algoritm real vaqtda ishlayotgan bo'lsa, O (N) ishlash har doim ham etarli bo'lmaydi. Odatda, N * log (N) murakkablikdagi algoritmlar yaxshi tezlikda ishlaydi. Insertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun biz uning narxini (operatsiyalar sonini) va ushbu satr har bir satrning yonida necha marta bajarilishini belgilaymiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = uzunlik [ A ] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, bu sonni t j bilan belgilaymiz . Davr ichidagi chiziqlar tekshiruvdan bir marta kam bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Satr qiymati c takrorlangan t marta hissa beradi c m operatsiyalar umumiy sonida (ammo, bu ibora ishlatilgan xotira hajmini hisoblash uchun ishlatilishi mumkin emas). Barcha qatorlarning hissalarini qo'shsak, olamiz Jarayonning ishlash vaqti nafaqat n ga bog'liq , balki kirishning kirish qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq . Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng maqbul holat. So'ngra line davr birinchi tekshirish keyin 5 tugaydi (buyon A [ i ] ≤ asosiy uchun i = j - 1), shuning uchun hamma narsani t j umumiy vaqti 1, va Shunday qilib, eng qulay holatda, vaqt t ( n ), hajmi bir qator saralash uchun zarur n, bir chiziqli funksiya (bo'lgan chiziqli funktsiyasi ) tomonidan n , masalan a va b ba'zi turg'unliklar uchun T ( n ) = a n + b shakli mavjud . Ushbu Sobit tanlangan qiymatlari orqali aniqlanadi bilan 1 , ... , bilan 8 . Agar qator teskari (pasayish) tartibda joylashgan bo'lsa, ish vaqti protsedura maksimal bo'ladi: A [ j ] har bir elementni A [1] , ..., A [ j - 1] barcha elementlar bilan taqqoslash kerak . Bundan tashqari, t j = j . Chunki biz eng yomon holatda protsedura vaqti ekanligini tushunamiz. Bunday holda, T ( n ) - kvadrat ( kvadratik funktsiya ), ya'ni. shakli mavjud T ( n ) = a n 2 + b n + s . A , b va c konstantalari bu erda c 1 , ..., c 8 qiymatlari bilan ham belgilanadi . Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n hajmi kirish ma'lumotlarining) n . Amaliyotda T ( n ) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun, ular yordamida asimptotik munosabatlar murojaat O -symbolics. Masalan, agar algoritm ishlashi uchun talab qilinadigan tadbirlar (harakatlar) soni 16 n 2 + 12 n log n + 2 n + 3 bilan ifodalangan bo'lsa , u holda algoritm T ( n ) ning O ( n 2 ) tartibida bo'lishini anglatadi. ) Asimptotik Omatikani shakllantirishda , barcha asl ifoda shartlari katta n uchun eng katta hissa qo'shadigan narsa bilan qoldiriladi (qolgan atamalar e'tiborsiz qoldirilishi mumkin) va uning oldidagi koeffitsient e'tiborga olinmaydi (chunki barcha asimptotik baholar doimiygacha berilgan). Belgilangan O () ishlatilganda, ular aniq bajarilish vaqtini anglatmaydi, balki faqat uning yuqori chegarasi, doimiy omilgacha. Masalan, algoritm O ( n 2 ) tartibining vaqtini talab qiladi deb aytganda , ular vazifaning bajarilish vaqti elementlar sonining kvadratidan tezroq o'smasligini anglatadi. O'rta va eng yomon ish |
