21
правка
Изменения
→Алгоритмы построения/восстановления
Ниже описанные алгоритмы работают за время О(n^2), но их можно ускорить до О(n*log(n)) ускорив процесс поиска, например двоичными деревьями.
{| width="150" align="right" cellpadding="5" border="1" style="border-collapse: collapse;"
|-
| <span style="font-size:smaller;">Получение таблицы инверсии из таблицы перестановки</span>
[5 9 1 8 2 6 4 7 3] - т. перестановки
[ 0]
[ 1 0]
[ 2 1 0]
[ 2 2 1 0]
[ 0 2 2 1 0]
[ 4 0 2 2 1 0]
[ 6 4 0 2 2 1 0]
[ 3 6 4 0 2 2 1 0]
[2 3 6 4 0 2 2 1 0] - т. инверсии
|-
| <span style="font-size:smaller;">Получение таблицы перестановки из таблицы инверсии</span>
[2 3 6 4 0 2 2 1 0] - т. инверсии
[9]
[9 8]
[9 8 7]
[9 8 6 7]
[5 9 8 6 7]
[5 9 8 6 4 7]
[5 9 8 6 4 7 3]
[5 9 8 2 6 4 7 3]
[5 9 1 8 2 6 4 7 3] - т. перестановки
|-}
== Алгоритм построения ==
