|
2- ma`ruza. Saralash algoritmlari. Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari
|
| bet | 9/9 | | Sana | 16.02.2024 | | Hajmi | 5,7 Mb. | | #157511 |
Bog'liq 2- ma`ruza(2023)1) boshlansin;
2) agar A = B bo‘lsa, N natija deb
olinsin va 6-bandga o‘tilsin;
3) A va B sonlarning kattasi aniqlansin;
4) A va B sonlarning kattasi o‘zi bilan kichik son-ning ayirmasiga teng deb olinsin;
5) 2-bandga o‘tilsin;
6) tugatilsin.
3-masala. ax² + bx + c = 0
ko‘rinishidagi kvadrat teng-lamaning yechimlarini topish algoritmiga mos blok-sxema tuzing.
Biz algoritmlarning chiziqli, tarmoqlanuvchi va takrorlanuvchi turlarini o‘rgandik. Inson hayotida uchraydigan algoritmlar, asosan, shu uch turdagi algoritmlarning uzviy birligi sifatida namoyon bo‘ladi.
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.
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.
O (n2) - kvadratik murakkablik. Bunday murakkablik, masalan, element qoʻshilishi natijasida yangi saralash algoritmiga ega. Kanonik dasturda bu ikkita ichki sikldan iborat: biri butun massivni bosib oʻtish, ikkinchisi esa allaqachon ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni n*n, ya‘ni n2 kabi massiv oʻlchamiga bogʻliq boʻladi.
E`tiboringiz uchun tashakkur!
|
| |
