Psevdokod
[ tahrirlash ]
Quyidagi kod ajratilgan ma'lumotlar tuzilmasi bilan amalga oshiriladi. U
F o'rmonini yo'naltirilmagan qirralarning to'plami sifatida ifodalaydi va ikkita cho'qqi
bir daraxtning bir qismi ekanligini samarali aniqlash uchun ajratilgan ma'lumotlar
strukturasidan foydalanadi.
Kruskal ( G ) algoritmi
F:=
∅
GVdagi har bir v uchun do
SOZLASH(v)
GEdagi har bir {u, v} uchun og‘irlik ({u, v}) bo‘yicha tartiblangan, agar
FIND-SET(u) ≠ FIND-SET(v) bo‘lsa , ortib boradi
F := F
∪
{ {u, v} }
UNION(FIND-SET(u), FIND-SET(v))
qaytish F
Murakkablik
[ tahrirlash ]
E qirralari va V cho'qqilari bo'lgan grafik uchun Kruskal algoritmini oddiy
ma'lumotlar tuzilmalari bilan O ( E log E ) vaqtida ishlashini ko'rsatish mumkin . Bu
yerda O vaqtni katta O belgisida ifodalaydi va log har qanday asosga logarifmdir
(chunki O-notatsiya ichidagi barcha asoslarning logarifmlari ekvivalentdir, chunki
ular doimiy omilgacha bir xil). Bu vaqt chegarasi ko'pincha uning o'rniga
O ( E log V ) ko'rinishida yoziladi , bu hech qanday ajratilgan uchlari bo'lmagan
grafiklar uchun ekvivalentdir, chunki bu grafiklar uchun
/ 2
2
V
E
V
va
V
va
E
logarifmlari yana doimiy omil doirasidadir.
Bu chegaraga erishish uchun avval
(
)
O E logE
vaqtida taqqoslashdan foydala-nib,
qirralarni og'irlik bo'yicha tartiblang . Saralangandan so'ng, har bir chekkada
doimiy
7
vaqt ichida tartiblangan tartibda chekkalarni aylanib o'tish mumkin. Keyin, har bir
komponent
uchun
cho'qqilar
to'plami
bilan ajratilgan
ma'lumotlar
tuzilmasidan foydalaning, qaysi cho'qqilar qaysi komponentlarda ekanligini kuzatib
boring. Har bir cho'qqi uchun alohida to'plam bilan ushbu tuzilmani yaratish
V
operatsiyalari va
( )
O V
vaqtini oladi. Barcha qirralarning yakuniy iteratsiyasi ikkita
topish amalini va, ehtimol, har bir chekkada birlashma amalini bajaradi. Ushbu
operatsiyalar har bir operatsiya uchun amortizatsiya qilingan vaqt O ( a ( V )) vaqtni
oladi va bu tsikl uchun eng yomon umumiy vaqt O ( E a ( V )) ni beradi , bu
erda a juda sekin o'sib boruvchi teskari Akkerman funktsiyasidir . Cheklangan
vaqtning bu qismi saralash bosqichi uchun vaqtdan ancha kichik, shuning uchun
algoritm uchun umumiy vaqtni saralash bosqichiga qadar soddalashtirish mumkin.
Qirralar allaqachon tartiblangan bo'lsa yoki butun sonlarni saralash
algoritmlariga, masalan, chiziqli vaqt ichida saralash imkonini beradigan darajada
kichik butun son og'irligiga ega bo'lsa , ajratilgan to'plam operatsiyalari algoritm-
ning eng sekin qolgan qismidir va umumiy vaqt O ( E a( V )) ga teng .
Foydalanilgan adabiyotlar:
1.
Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд
Штайн. Алгоритмы: построение и анализ. Москва-Санкт-Петербург-Киев.
Изд. дом «Вильямс», 2003. 1293 стр.
2.
Levetan Anany. Introduction to the design & analisis of algorithms. 3rd
ed. Villanova university. New Jersey. 2012. 693 page.
3.
Род Стивенс. Готовые алгоритмы. М.: ДМК Пресс. Питер 2004. 384
стр.
4.
Стивен Скиены. Алгоритмы. Руководство по разработке. Питер
2011. 715 стр.
|
