Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17
OHW: Rozdiel medzi revíziami
Z VPDS
(Vytvorená stránka „Nepovinná domáca úloha ==A (2 body)== Uvažujme Morissov-Prattov algoritmus pre vzorku P dĺžky m, ktorý bežíme na veľmi dlhom texte T. Koľko najviac bude trva...“) |
(Žiaden rozdiel)
|
Verzia zo dňa a času 14:10, 6. apríl 2016
Nepovinná domáca úloha
A (2 body)
Uvažujme Morissov-Prattov algoritmus pre vzorku P dĺžky m, ktorý bežíme na veľmi dlhom texte T. Koľko najviac bude trvať spracovanie úseku dĺžky k niekde uprostred textu T ako funkcia parametrov m a k? Hodnota k môže byť menšia alebo väčšia ako m. Uveďte aszmptotický horný aj dolný odhad, t.j aj príkald, kde to bude trvať
