10
правок
Изменения
Нет описания правки
{{Определение|definition ='''Преобразование MTF''' (англ. ''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования.}}
== Описание алгоритма ==
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>N</tex> {{---}} размер алфавита, <tex>M</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N</tex><tex>\log</tex><tex>M)</tex>.
== Описание алгоритма за O(NlogN log(N+M)) ==
=== Идея ===
'''list<int>''' result(N)
'''list<int>''' used(N+M)
'''for''' i = 1 '''to''' M <font color=darkgreen>//Заполняем последние N M ячеек единицами</font color=darkgreen>
used[i+N] = 1
'''for''' i = 1 '''to''' N
