|
Primo algoritmi samaradorligi
|
| bet | 4/4 | | Sana | 14.05.2024 | | Hajmi | 0,98 Mb. | | #230833 |
Bog'liq MBma`ruza1Primo algoritmi samaradorligi - Samaradorlik grafni tashkil etish va minimal narxli daraxtga tegishli bo’lmagan tugunlarni saqlash usuliga bog’liq.
- Agar Q navbat massiv ko’rinishida tashkil etilsa, Extract.Min(Q) amali O(n) ga bog’liq va minimal vaznli yoylarni daraxtga o’zlashtirishga O(1) ta amal sarflanadi.
- Agar Q navbat binar piramida ko’rinishida tashkil etilsa, u xolda Extract.Min(Q) amali O(log(n)) gacha kamayadi.ammo minimal vaznli yoylarni daraxtga o’zlashtirish amali miqdori O(log(n)) ga oshadi.
Kruskal algoritmi - Algoritm dastlab 1956 yilda Jozef Kruskal tomonidan taklif etilgan.
- Dastlab yoylarning boshlang’ich to’plami bo’sh deb olinadi.
- Keyin, imkoni bo’sa, quyidagi amal bajariladi:
- Mavjud yoylar qarab chiqiladi, ularni daraxtga qo’shganda xalqa xosil bo’lmaydigan bo’lsa, ularning vazni minimali olinadi va daraxtga qo’shiladi.
- Agar bunday yoylar bo’lmasa, algoritm tugallanadi.
- Graf tugunlaridan xosil bo’lgan qismgraf minimal narxli daraxt xisoblanadi.
Algoritmga misol
tasvir
|
izox
| | |
AD va CE yoylar minimal vaznga ega - 5. ixtiyoriy bittasi tanlanadi., masalan AD
| | |
Keyingi kichikroq yoy 5 - CE. Yoyi xisoblanadi. Uni tanlanganda xalqa xosil bo’lmaydi.
| | |
Vazni 6 ga teng bo’lgan DF yoyi tanlanadi.
| Algoritmga misol
tasvir
|
izox
| | |
AB va BE yoylar vazni 7. AB ni ixtiyoriy tanlaymiz, BD yoy tanlanmaydi, chunki ABD xalqa xosil bo’lishi mumkin.
| | |
Vazni 7 bo’lgan BE yoy tanlanadi. BC yoy olinmaydi, chunki BCE xalqa, DE xam olinmaydi, chunki DEBA xalqa, FE xam olinmaydi, chunki FEBAD xalqa.
| | |
Vazni 9 bo’o’lgan EG yoy qo’shiladi va algoritm tugullanadi. Minimal narxli daraxt aniqlandi.
| Kruskal algoritm samaradorligi - Algoritm boshlanishidan avval yoylarni vazni bo’yicha saralab chiqish talab etiladi. Buning uchun O(E × log(E)) vaqt talab etiladi. Qolgan vaqt yoylarni daraxtga qo’shish uchun sarflanadi.
- Kruskal algoritmida vaqt asosan saralashga sarflanishi sababli samaradorlikni O(E × log(E)) deb olish mumkin.
E`TIBORINGIZ UCHUN RAHMAT
|
| |
