Aufwand Spracherkennung

Question

Hallo

In der nuKIT Umfrage zu Kapitel 3 ist bei der siebten Frage als richtig vermerkt :
1. Der Aufwand zur Spracherkennung bei deterministischen Kellerautomaten ist linear in der Wortlänge.
Weiter ist auch richtig :
2. Der Aufwand zur Spracherkennung bei deterministischen Kellerautomaten ist $O(n^3)$.

Wie können diese Antworten denn zusammenpassen?

Comments

Na ja, was genau heißt denn $O(n^3)$? Schreiben Sie das mal genau (in eigenen Worten) hin: In $O(n^3)$ liegen alle Funktionen, die...???

(Dann werden Sie sehen, dass da die linearen auch dabei sind...)

---

Ist übrigens ein typischer Informatiker-Trick, die Leute mit so einer Formulierung zu verwirren ;-)

Aber wenn man es einmal verstanden hat, macht man es auch selber gerne.