Время работы

[SokG2000]

https://github.com/alresin/formal_langs_practicum/blob/78e2d7bddd98a999aae2b7d0fe81e03c68ab15e9/earley.py#L69 Оно точно работает O(|w|^3)?

[alresing]

Работает по алгоритму, обсужденному на семинарах и лекциях.

Где в основном идет:

while changes:
    complete()
    predict()

for letter in word:
    scan()
    while changes:
        complete()
        predict()

Насколько я понял, в файле не написано нигде, что необходимо реализовать за O(|w|^3). Поэтому был реализован вариант обсужденный на семинарах и лекциях.

[SokG2000]

В файла написано, что нужно реализовать алгоритм Эрли, а алгоритм Эрли работает за O(|w|^3). Лекции этого года я не смотрел, но на семинаре точно обсуждалось как этого добиться

[alresing]

Да, на семинарах обсуждалось устно, но псевдокод, который был на семинаре написан, явно соответствует данному алгоритму, и он работает не за O(|w|^3). В файле просто не указана явно асимптотика. Но видимо подразумевалась быстрая версия, окей значит перепишу.

[alresing]

Переписал код с аналога обсужденного псевдокода на тот, что работает за O(|w|^3).