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 Obě strany příští revize | ||
mgr-szz:in-pos:2-pos [2019/06/13 08:12] lachmanfrantisek algoritmy do boxů |
mgr-szz:in-pos:2-pos [2019/06/13 08:15] lachmanfrantisek |
||
---|---|---|---|
Řádek 381: | Řádek 381: | ||
| Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>O((n-m+1)m)</math> | | | Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>O((n-m+1)m)</math> | | ||
- | * Průměrná složitost je výrazně lepší. | + | * Očekávaná složitost je výrazně lepší. |
<box 100% blue|Karp-Rabin> | <box 100% blue|Karp-Rabin> | ||
Řádek 396: | Řádek 396: | ||
- Posuneme se o jednu pozici v prohledávaném textu a přepočteme haš (v konstantním čase). | - Posuneme se o jednu pozici v prohledávaném textu a přepočteme haš (v konstantním čase). | ||
- Porovnáváme a posouváme se dokud jsme nedosáhli <math>(m-1)</math>-té pozice od konce. Poté vrátíme všechny nalezené pozice. | - Porovnáváme a posouváme se dokud jsme nedosáhli <math>(m-1)</math>-té pozice od konce. Poté vrátíme všechny nalezené pozice. | ||
+ | |||
+ | * Očekávaná složitost pro //c// nálezů: <math>\mathcal{O}((n-m+1) + cm)</math> | ||
+ | * ➕ vhodné pro delší vzorky s malým počtem očekávaných nálezů | ||
</box> | </box> | ||