|
Qiyinchilik funktsiyasi O (Log 2 (A0), 0 (N log 2 (A0). Bunday vaqt davomida algoritmlar ishlaydi, bu katta muammoni koʻplab kichiklarga ajratadi va keyin ularni echib, echimlarni birlashtiradi.
Murakkablik funktsiyasi 0 (e N). Koʻrsatkichli murakkablikdagi algoritmlar koʻpincha qoʻpol kuch deb nomlangan yondashuvdan kelib chiqadi.
Qiyinchilik funktsiyasi 0 (M) - operatsiyalar soni faktorialga mutanosib ravishda oʻsib boradi N.
Dasturchi algoritmlarni tahlil qila olishi va ularning murakkabligini aniqlay olishi kerak. Algoritmning vaqt murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida hisoblash mumkin.
Davrsiz va rekursiv chaqiriqlarsiz algoritmlar doimiy murakkablikka ega. Agar rekursiya va tsikl boʻlmasa, barcha boshqaruv tuzilmalari doimiy ravishda murakkablikdagi tuzilmalarga aylantirilishi mumkin. Binobarin, butun algoritm doimiy murakkablik bilan ham ajralib turadi. Algoritmning murakkabligini aniqlash asosan tsikllar va rekursiv chaqiruvlarni tahlil qilishgacha kamayadi.
Masalan, massiv elementlarini qayta ishlash algoritmini koʻrib chiqing.
Uchun / ": \u003d 1 dan N boshlang
Ushbu algoritmning murakkabligi HAQIDA (A), chunki tsikl tanasi A marta bajarilgan va tsikl tanasining murakkabligi 0 (1) ga teng. Agar bitta tsikl boshqasiga joylashtirilgan boʻlsa va ikkala tsikl bir xil oʻzgaruvchining oʻlchamiga bogʻliq boʻlsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi.
Uchun /: \u003d 1 dan N uchun qiling j: \u003d 1 dan N boshlang
Ushbu dasturning murakkabligi 0 (N 2).
1-misol. Klaviaturadan massivni kiritadigan va undagi eng katta elementni topadigan dasturning murakkabligini taxmin qilaylik. Algoritm quyidagi bosqichlardan iborat:
- massivni kiritish (A elementlarini oʻqish kerak);
- eng katta elementni qidirish (A - 1 taqqoslashni amalga oshirish kerak);
- natijaning chiqarilishi (bitta raqam yoki qatorni chiqarish kerak).
A + (A - 1) + 1 \u003d 2A operatsiyalar sonini qoʻshamiz, yaʻni. mavjud
har qanday A uchun amallar soni CA dan oshmaydigan doimiylik. Shuning uchun algoritmning murakkabligi 0 (A) ga teng.
2-misol. Klaviaturadan massivni kiritadigan va unda berilgan xususiyatga ega elementni (masalan, maʻlum bir qiymatga teng) topadigan dasturning murakkabligini baholaylik. Algoritm quyidagi bosqichlardan iborat:
- massivni kiritish (Kiritish operatsiyalari);
- berilgan xususiyatga ega elementni qidirish (element massivning boshiga yaqinroq yoki oxirida joylashgan boʻlishi mumkin; agar element mavjud boʻlmasa, bunga ishonch hosil qilish uchun barcha A taqqoslashlari kerak)
- natijaning chiqishi.
Eng yaxshi holatda, koʻrsatilgan algoritm uchun A + 2 operatsiyalari (butun massivni kiritish, bitta taqqoslash, chiqish), eng yomoni (bunday element boʻlmaganida, 2A + 1 amal) kerak boʻladi. Agar A katta raqam boʻlsa, masalan, taxminan 10 6, birlikni eʻtiborsiz qoldirish mumkin. Shuning uchun algoritmning murakkabligi 0 (N).
3-misol. Uzunlik soʻzi uchun shifrlash algoritmining murakkablik funktsiyasini aniqlaylik L almashtirish usuli. Jadval boʻlsin, unda alfavitning har bir belgisi uchun uni almashtirish kerak boʻlgan belgi yoziladi. Keling, alifbo harflari sonini belgilaylik S. Algoritm quyidagi bosqichlardan iborat:
- soʻzlarni kiritish (bitta operatsiya);
- tsiklni tashkil etish:
1) har bir belgi uchun uning oʻrnini jadvalda toping (agar jadval buyurtma qilinmasa va qidirishni osonlashtiradigan xususiyatlarga ega boʻlmasa, unda eng yomon holatda sizga kerak boʻladi S agar kerakli element eng oxirida boʻlsa, bitta belgi uchun operatsiyalar);
2) topilgan belgining chiqishi;
- tsikl tugashi.
Jami operatsiyalar soni 1 + (S +) L. Agar etarlicha katta boʻlsa S va L birliklarni eʻtiborsiz qoldirish mumkin va bu berilgan algoritmning murakkabligi funktsiyasi shunday boʻlib chiqadi O (S L).
4-misol. Natural sonlarni tarjima qilish algoritmining murakkabligini aniqlaylik 1 Ikkilik tizimga V (maʻlumotlarni kiritish va chiqarish operatsiyalari yoʻq). Algoritm quyidagi bosqichlardan iborat:
- raqamni 2 ga boʻlish natijasi 0 boʻlguncha tsikl:
- sonni 2 ga boʻling va qolganini eslang;
- boʻlinish natijasini yangi raqam sifatida qabul qilish;
- tsikl tugashi.
Amaliyotlarning umumiy soni 1 + log 2 A dan oshmaydi, shuning uchun tavsiflangan algoritm murakkablikka ega 0 (og 2 N).
Algoritmlar nazariyasining asoslarini bilish har qanday dasturchi uchun juda muhimdir, chunki aynan shu fan algoritmlarning umumiy xususiyatlarini va ularni namoyish etishning rasmiy modellarini oʻrganadi. Hatto informatika darslaridan boshlab, biz oqim jadvallarini tuzishga oʻrgatamiz, bu keyinchalik maktabga qaraganda ancha murakkab masalalarni yozishda yordam beradi. Bundan tashqari, maʻlum bir muammoni hal qilishning deyarli har doim bir necha yoʻli borligi sir emas: baʻzilari koʻp vaqt, boshqa resurslarni sarflashni oʻz ichiga oladi, boshqalari esa faqat taxminan echim topishga yordam beradi.
Siz har doim topshiriqga muvofiq ravishda eng maqbul narsani izlashingiz kerak, xususan, muammolar sinfini hal qilish algoritmlarini ishlab chiqishda.
Algoritmni har xil hajm va miqdorlarning boshlangʻich qiymatlari bilan qanday ishlashini, qanday manbalarga ehtiyoj borligini va yakuniy natijani chiqarish uchun qancha vaqt ketishini baholash ham muhimdir.
Bu algoritmlar nazariyasining bir boʻlimi - algoritmlarni asimptotik tahlil qilish nazariyasi.
Men ushbu maqolada asosiy baholash mezonlarini tavsiflashni va eng oddiy algoritmni baholashga misol keltirishni taklif qilaman. Habrahabrda allaqachon algoritmlarni baholash usullari mavjud, ammo u asosan litsey oʻquvchilariga qaratilgan. Ushbu nashrni ushbu maqolaning chuqurlashishi deb hisoblash mumkin.
Do'stlaringiz bilan baham: |
