23. Floyda algoritmi


Binar indekslengen terek (Fenwick algorithm)



Download 243,83 Kb.
bet5/5
Sana13.12.2022
Hajmi243,83 Kb.
#885073
1   2   3   4   5
31. Binar indekslengen terek (Fenwick algorithm)
Binar indekslengen terek yamasa Fenwick teregi massivtiń dinamikalıq variantı bolıp tabıladı.
Ol massivte eki O(logn) waqıtlı ámeller qabıl etedi: aralıq sorawlardı esaplaw hám bahalardı jańalaw. Binar terektiń abzallıǵı sonda ol bizge nátiyjeli túrde massiv bahaların ózgertiw imkaniyatın beredi. Bunı massiv arqalı ámelge asırıp bolmaydı, sebebi hár bir update den keyin O(n) waqıt sarplap jańa massiv payda etiwge tuwra keledi.
Segment terek
Segment tree eki ámel qabıl etetuǵın maǵlıwmatlar strukturası bolıp tabıladı: aralıq sorawdı ámelge asırıw hám massiv ma`nisin update qılıw. Segment terekler jıyındı sorawı, minimum soraw, maksimum soraw hám sol sıyaqlı basqa sorawlardı qabıl etedi jáne bulardıń barlıǵında O(logn) waqıtlı eki ámelden paydalanadı. Binar indekslengen terekke salıstırılatuǵın bolsaq, segment terekti abzallıǵı sonda ol ulıwma struktura bolıp tabıladı. Binar indekslengen terek tek jıyındı sorawları ushın islese, segment terek basqa soraw túrlerin da óz ishine aladı. Biraq segment terek kóbirek yad talap etedi hám ámelge asırıw azmaz qıyınlaw.

32. Union-Find Algorithm
Yo'naltirilmagan grafikda cikl bar yamasa joq ekenligin tekseriw ushın Union-Find algoritmınan paydalanıw múmkin. Itibar beriń, biz cikldı anıqlaw algoritmın talqılaw etdik. Bul Union-Find-ga tiykarlanǵan taǵı bir usıl. Bul usıl grafikda óz-ózinen aylanıwlar joq ekenligin shama etedi.

C# kodi
// Naive implementation of find
static int find(int []parent, int i)
{
if (parent[i] == -1)
return i;
 
return find(parent, parent[i]);
}
 
// Naive implementation of union()
static void Union(int []parent, int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
 
// This code is contributed by pratham76
Python dagi kodi
# Naive implementation of find
def find(parent, i):
 
if (parent[i] == -1):
return i
 
return find(parent, parent[i])
 
# Naive implementation of union()
def Union(parent, x, y):
 
xset = find(parent, x)
yset = find(parent, y)
parent[xset] = yset
 
# This code is contributed by rutvik_56

33. Quick Union Find algoritmi
Download 243,83 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©www.hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish