hledat
Rozdíly
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 | ||
|
mgr-szz:in-pos:2-pos [2019/06/13 10:53] lachmanfrantisek poznámka a odkaz na video k Fibonacciho haldě |
mgr-szz:in-pos:2-pos [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 329: | Řá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)> | ||
| Řádek 380: | Řádek 387: | ||
| ^ Algoritmus ^ Předspracování ^ Vyhledávání ^ | ^ Algoritmus ^ Předspracování ^ Vyhledávání ^ | ||
| - | | Úplné prohledávání | <math>O</math> | <math>O((n-m+1)m)</math> | | + | | Úplné prohledávání | <math>O</math> | <math>\mathcal{O}((n-m+1)m)</math> | |
| - | | Karp-Rabin * | <math>\Theta(m)</math> | <math>O((n-m+1)m)</math> | | + | | Karp-Rabin * | <math>\Theta(m)</math> | <math>\mathcal{O}((n-m+1)m)</math> | |
| - | | Konečné automaty | <math>O(m |\Sigma|)</math> | <math>\Theta(n)</math> | | + | | Konečné automaty | <math>\mathcal{O}(m |\Sigma|)</math> | <math>\Theta(n)</math> | |
| | Knuth-Morriss-Pratt | <math>\Theta(m)</math> | <math>\Theta(n)</math> | | | Knuth-Morriss-Pratt | <math>\Theta(m)</math> | <math>\Theta(n)</math> | | ||
| - | | Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>O((n-m+1)m)</math> | | + | | Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>\mathcal{O}((n-m+1)m)</math> | |
| * Očekávaná složitost je výrazně lepší. | * Očekávaná složitost je výrazně lepší. | ||
