К>>> лукохеды могут очень жёстко просадить производительность. Сделать квадратичную — легко. Сделать кубическую — чуть сложнее (двойное отрицание).
AS>>нет. при ненаивной реализации можно обеспечить линейную. И ненадо меня убеждать, что нельзя.
К>Есть что почитать на эту тему? Или на пальцах объяснить?
Это я мало подумал. Теперь думаю, что сложность будет кубическая от длины текста, помноженная на количество правил в грамматике (
алгоритм CYK).
