Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze Následující verze Obě strany příští revize | ||
mgr-szz:in-pos:2-pos [2019/06/13 09:59] lachmanfrantisek Boyer-Moore |
mgr-szz:in-pos:2-pos [2019/06/17 10:21] lachmanfrantisek |
||
---|---|---|---|
Řádek 285: | Řádek 285: | ||
* struktura může obsahovat víc stromů; ukládáme ukazatel na minimální prvek | * struktura může obsahovat víc stromů; ukládáme ukazatel na minimální prvek | ||
* odkládáme operace až na dobu, kdy je to nutné | * odkládáme operace až na dobu, kdy je to nutné | ||
+ | * dvě hlavní mota (viz video [[https://www.youtube.com/watch?v=CEvUqy1uF1E|Amortized analysis of Fibonacci heap]]): | ||
+ | * //Někdy se vyplatí nechat nepořádek narůst. (A uklidit hromadně.)// | ||
+ | * = Nové uzly přidáváme jako jednouzlové stromy. Stromy se stejným stupněm spojujeme hromadně až při ''extract-min''. | ||
+ | * //Tvoji rodiče chtějí hodně vnoučat a pokud nemáš moc dětí, tak tě zavrhnou.// | ||
+ | * = Uzel, který již dvakrát ztratil při ''decrease-key'' potomka je přesunut jako nový strom. | ||
* Efektivně realizujeme UNION, INSERT a DECREASE_KEY, ale nezhoršujeme amortizovanou složitost ostatních operací. | * Efektivně realizujeme UNION, INSERT a DECREASE_KEY, ale nezhoršujeme amortizovanou složitost ostatních operací. | ||
Řádek 324: | Řádek 329: | ||
* komponenty souvislosti | * komponenty souvislosti | ||
* ekvivalence konečných automatů | * ekvivalence konečných automatů | ||
+ | |||
+ | ^ algoritmus ^ MAKE_SET ^ UNION ^ FIND_SET ^ | ||
+ | | reverzní stromy | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(n)</math> | | ||
+ | | reverzní stromy (optimalizace) | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(\log n)</math> | <math>\mathcal{O}(\log n)</math> | | ||
+ | | plytké stromy | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(\log n)</math> | <math>\mathcal{O}(1)</math> | | ||
+ | |||
+ | Stromy s kompresí: Posloupnost m operací UNION, FIND_SET a MAKE_SET, z toho n operací MAKE_SET má složitost <math>O(m . \alpha(n))</math> | ||
<box 100% blue|Reverzní stromy (Reversed trees)> | <box 100% blue|Reverzní stromy (Reversed trees)> |