|
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
| bet | 7/9 | | Sana | 17.05.2024 | | Hajmi | 48,86 Kb. | | #240309 |
Bog'liq 1-MavzuMurakkablikni baholash. Algoritmlarning murakkabligi odatda bajarilish vaqti yoki ishlatilgan xotira boʻyicha baholanadi. Ikkala holatda ham, murakkablik kiritilgan ma’lumotlarning hajmiga bogʻliq: 100 ta elementdan iborat massivi xuddi shunga oʻxshash 1000 ta elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Shu bilan birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorga bogʻliq, ma’lumotlar turi, dasturlash tili va boshqa koʻplab parametrlarga ham bogʻliq. Faqatgina asimptotik murakkablik muhim, ya’ni kirish ma’lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik.
Masalan, ba’zi bir algoritmga kirish ma’lumotlarining n ta elementlarini qayta ishlash uchun 4n3 + 7n ta shartli amallarni bajarish kerak. n ning ortishi bilan ishning umumiy davomiyligi n ning kubi uni 4 ga koʻpaytirgandan yoki 7n ni qoʻshgandan koʻra koʻproq ta’sir qiladi. Ushbu algoritmning vaqt murakkabligi O(n3), ya’ni u kubik bilan kiritilgan ma’lumotlarning hajmiga bogʻliq boʻladi.
Bosh harf O dan foydalanish matematikadan kelib chiqadi, bu yerda ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki egallagan xotira miqdori), kiritilgan ma’lumotlarning hajmiga qarab, f(n) ga koʻpaytiriladigan ba’zi konstantalardan tezroq emasligini anglatadi.
O (n) - chiziqli murakkablik. Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan oʻtishimiz kerak boʻladi.
O (log n) - logaritmik murakkablik. Eng oddiy misol - ikkilik qidirish. Agar massiv saralangan boʻlsa, uni yarmiga boʻlish orqali ma’lum bir qiymatga ega ekanligini tekshirishimiz mumkin. Oʻrta elementni tekshirib koʻramiz, agar u kattaroq boʻlsa, unda massivning ikkinchi yarmini tashlab yuboramiz. Agar kichikroq boʻlsa, unda aksincha - biz dastlabki yarmini tashlaymiz va shu tarzda ikkiga boʻlinishni davom ettiramiz, natijada (logn) elementlarini tekshiramiz.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
