Кто подскажет, какая (асимптотическая) сложность у данных алгоритмов (в зависимости от входных данных) при декодировании кодов Рида-Соломона?
У Блейхута, вроди, написано, что Евклид имеет сложность

, а Берлекэмп-Месси -

. Но везде написано, что алгоритм БМ работает быстрее. Наверное, я что-то не так прочитал... Подскажите, пожалуйста, очень нужно! Спасибо!