Вернуться к статье
метод декодирования кодов Рида-Соломона на основе коррекции ошибок и стираний для биометрических систем
Сводная таблица вычислительной сложности стратегий декодирования
*относительно базовой с кратным (×) увеличением времени обработки; ** – количество пользователей (хранение индивидуальных профилей)
Стратегия | Память | Попыток декодирования (ср./макс) | Доп. вычисления | Относительное время* |
Базовая | O(n) | 1,0/1 | нет | 1,0× |
Фиксированная | O(n) | 1,0/1 | линейный проход O(n) | 1,1-1,2× |
Интеллектуальная (упрощенная) | O(n) | 1,15/42 | 1 сортировка O(n logn)+fall-back | 2,0-2,5× |
Интеллектуальная (полная) | O(n∙m)** | 1,15/42 | 50×betainv+сорти-ровка | 50-100× |
Комбинированная | O(n) | 1,5/3 | 2-3 сортировки O(n logn) | 1,5-3,0× |