2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Евклид против Берлекэмпа-Месси
Сообщение04.12.2012, 02:18 
Кто подскажет, какая (асимптотическая) сложность у данных алгоритмов (в зависимости от входных данных) при декодировании кодов Рида-Соломона?
У Блейхута, вроди, написано, что Евклид имеет сложность $O(n\ln ^2 n)$, а Берлекэмп-Месси - $O(n^2)$. Но везде написано, что алгоритм БМ работает быстрее. Наверное, я что-то не так прочитал... Подскажите, пожалуйста, очень нужно! Спасибо!

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group