Diskussion:Berry-Sethi-Verfahren

Eine genauere Definition der Attribute empty, first, next und last wäre wünschenswert. -- 93.135.26.244 14:19, 28. Jan. 2009 (CET)Beantworten

Wie kommt man denn hier auf ${\mathcal {O}}(n^{3})$ ? Ich seh nur ${\mathcal {O}}(n^{2})$ : Die DFSs sind alle linear, d.h. Punkte 1-4 laufen linear schnell. Punkt 5.1-5.3 ist ein linearer Durchlauf durch eine Menge. Punkt 5.4. ist ein Durchlauf durch alle Next[i] Mengen -> Das ist bestenfalls quadratisch (nicht signierter Beitrag von 85.181.85.236 (Diskussion | Beiträge) 09:59, 18. Apr. 2010 (CEST)) Beantworten

Die Zeitkomplexität ist auch Quadratisch. Siehe dafü auch: Anne Brüggemann-Klein: Regular expressions into finite automata. In: Theoretical Computer Science 120, 1993, S. 197-213 (nicht signierter Beitrag von 2A02:908:4F2:A100:C2B7:9516:C4C1:1B2D (Diskussion | Beiträge) 08:22, 15. Jan. 2017 (CET))Beantworten

Abschnitt hinzufügen