From ef5e1d7a5baa07d16090acc3d98c1262ce0b9d40 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 15 Jan 2024 14:52:28 +0100 Subject: [PATCH] =?utf8?q?MST:=20Vysv=C4=9Btlen=C3=AD=20\alpha(n)?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 5-mst/5-mst.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index e77eb02..acd5aff 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -215,8 +215,8 @@ je maximální na~nějakém cyklu tvořeném touto hranou a nějakými dříve p Potřebujeme čas $\O(m \log n)$ na~setřídění hran a dále datovou strukturu pro udržování komponent souvislosti (Union-Find Problem), se~kterou provedeme $m$~operací \ a $n$ operací \. Nejlepší známá implementace -této struktury dává složitost obou operací $\O(\alpha(n))$ amortizovaně, takže celkově hladový algoritmus -doběhne v~čase $\O(m \log n + m \alpha(n))$. +této struktury dává složitost obou operací $\O(\alpha(n))$ amortizovaně, kde $\alpha$ je inverzní Ackermannova +funkce. Celkově tedy hladový algoritmus doběhne v~čase $\O(m \log n + m \alpha(n))$. \ss{Borůvkův:} -- 2.39.2