Таблица инверсий — различия между версиями

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

Версия 00:43, 26 ноября 2010

Пусть [math] P = (p_1,p_2,\dots,p_n)[/math] является перестановкой чисел [math] 1, 2,\dots, n[/math].


Определение:
Инверсией в перестановке [math]P[/math] называется всякая пара индексов [math]i, j[/math] такая, что [math]1\leqslant i\lt j\leqslant n[/math] и [math]P[i]\gt P[j][/math].


Определение:
Таблицей инверсий перестановки [math] P [/math] называют такую последовательность [math] T = (t_1,t_2,\dots,t_n)[/math], в которой [math]t_i[/math] равно числу элементов перестановки [math] P [/math], стоящих в [math] P [/math] левее числа [math]i[/math] и больших [math]i[/math].


Алгоритмы построения/восстановления

Ниже описанные алгоритмы работают за время О(n^2), но их можно ускорить до О(n*log(n)) ускорив процесс поиска, например двоичными деревьями.

Получение таблицы инверсии из таблицы перестановки
[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] - т. инверсии

Алгоритм построения

Для получения таблицы инверсий из таблицы перестановки вводим таблицу равной по длине таблице перестановки(не умаляя общности длина равна n) и на n-ное место записываем 0; ищем число i (от n-1 до 1) в таблице перестановки, и смотрим: сколько чисел больше i находится слева от числа i, полученное число записываем в таблицу инверсий на i-тое место.

Алгоритм восстановления

Для восстановления таблицы перестановки из таблицы инверсий(не умаляя общности длина таблицы равна n) создаем таблицу, которую будем расширять, по мере добавления в неё чисел, добавляем в эту таблицу число i (где i от n до 1) на позицию k+1, где k - число в таблице инверсий на i-том месте.

Получение таблицы перестановки из таблицы инверсии
[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] - т. перестановки