|
Referat tekshirdi: Vaffoyev Sunnatillo Mustaqil ish
|
| bet | 4/4 | | Sana | 18.05.2024 | | Hajmi | 221,49 Kb. | | #243271 | | Turi | Referat |
Bog'liq Algoritm-ReferatN jurnali N N
Chetlarni saralash Union-Find operatsiyalari
N + M —
Jami vaqt murakkabligi
Vaqtning murakkabligini taqsimlash
Birinchi qadam, qirralarni saralash, vaqt murakkabligi O(N log N), bu erda N - grafikdagi qirralarning soni. Ushbu saralash bosqichi odatda O(N log N) vaqt murakkabligiga ega bo'lgan tezkor saralash yoki birlashtirish kabi samarali tartiblash algoritmi yordamida amalga oshiriladi.
Ikkinchi qadam tsikllarni aniqlash va cho'qqilarning ulanishini kuzatish uchun ishlatiladigan Union-Find ma'lumotlar strukturasi operatsiyalarini o'z ichiga oladi. Union-Find operatsiyalarining vaqt murakkabligi O(N), bu erda N - grafikdagi cho'qqilar soni. Bu ko'pincha yo'lni siqish va daraja bo'yicha birlashtirish kabi usullardan foydalangan holda, deyarli doimiy vaqt operatsiyalarini amalga oshirishga imkon beruvchi Union-Find ma'lumotlar strukturasini samarali amalga oshirish bilan bog'liq.
Ikki asosiy bosqichning vaqt murakkabligini birlashtirgan holda, Kruskal algoritmining umumiy vaqt murakkabligi O (N + M) ga teng, bu erda N - cho'qqilar soni va M - grafikdagi qirralarning soni. Ushbu samarali vaqt murakkabligi Kruskal algoritmini katta, vaznli, yo'naltirilmagan grafiklarning minimal chegaralangan daraxtini topish uchun mashhur tanlovga aylantiradi, chunki u nisbatan qisqa vaqt ichida, hatto ko'p sonli uchlari va qirralari bo'lgan grafiklar uchun ham bajarilishi mumkin.
|
| |
