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 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:39] 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> | ||
| Řádek 402: | Řádek 405: | ||
| * Využití sufixové funkce <math>\sigma</math> určující délku nejdelšího prefixu vzorku, který je sufixem slova. | * Využití sufixové funkce <math>\sigma</math> určující délku nejdelšího prefixu vzorku, který je sufixem slova. | ||
| * <math>\delta(q, a) = \sigma(P[1] ... P[q] a)</math> | * <math>\delta(q, a) = \sigma(P[1] ... P[q] a)</math> | ||
| - | * Existuje procedura s <math>O(m|\Sigma|)</math> | + | * Tato metoda v <math>\mathcal{O}(m^3 \times \mid\Sigma\mid)</math>. |
| + | * Existuje procedura s <math>\mathcal{O}(m \times \mid\Sigma\mid)</math>. | ||
| * Text zpracujeme konečným automatem. <math>\Theta(n)</math> | * Text zpracujeme konečným automatem. <math>\Theta(n)</math> | ||
| </box> | </box> | ||
