Důkaz - Složitost Aho-Corasick

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Důkaz - Složitost Aho-Corasick

Příspěvek od Ellrohir »

mohl by mi někdo poradit, kde najdu srozumnitelně (a nejlépe česky - anglicky sice rozumím dobře, ale učit se v aj mi moc nejde) vysvětlený důkaz složitosti algoritmu Aho-Corasick? protože Kučera nemá v textech k algovizi vůbec nic a Marešovy skripta tam je cosi o násobení polynomů, což nějak nechápu jak souvisí s AC...
Návštěvník

Re: Důkaz - Složitost Aho-Corasick

Příspěvek od Návštěvník »

V zapiskoch z Maresovej prednasky ( http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps ) to myslim je.

Btw ten dokaz zlozitosti prace interpreteru spociva v tom, ze si uvedomis, ze na to, aby si k-krat zavolal funkciu fail musis najprv k-krat zavolat funkciu g, pretoze g ta v automate posuva o hladinu dalej od stavu 0, naopak fail ta posuva aspon o jednu hladinu blizsie k stavu 0. Inymi slovami celkovy pocet zavolani fail je mensi rovny celkovemu poctu zavolani g. No a g sa vola vola pre kazdy nacitany znak raz => celkovo sa vola m-krat ( kde m je velkost prehladavaneho textu ).

Snad som to nedoplietol :)
Magog
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 18. 3. 2008 19:36
Typ studia: Informatika Bc.

Re: Důkaz - Složitost Aho-Corasick

Příspěvek od Magog »

Ahaaa, tak takhle to je. Diky za tip.
J.M. Bloudil

Re: Důkaz - Složitost Aho-Corasick

Příspěvek od J.M. Bloudil »

Selsky duKaz: Kdyz lezes na strom (i opakovane), spadnes nanejvys z te vysky kam jsi vylezl.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“