1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''for''' i = 1..n
'''for''' j = 1..(i - 1)
'''if''' P}[j] > P}[i]
T[P[i]] = T[P[i]]++
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |сортировке слиянием.]]
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов второго первого списка.
Описанный алгоритм записывается в псевдокод следующим образом:
<font color=green>// ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font>
<font color=green>// ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font>
'''def''' inverses_merge(ls1, ls2)}:
result = []
it1, it2 = ''null''
'''while''' (it1 < ls1.length) '''and''' (it2 < ls2.length): '''if''' ls1[it1}].item < ls2[it2].item:
result.append(ls1[it1])
it1++
'''else:'''
result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + ls1.length - it1)
it2++
'''while''' it1 < ls1.length):
result.append(ls1[it1])
it1++
'''while''' (it2 < ls2.length):
result.append(ls2[it2])
it2++
'''return''' result
'''def''' inverses_get(ls)}:
'''if''' ls.length == 1
'''return''' [(item = ls[0], inverses = 0)]
'''else:'''
'''return''' inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью [[Дерево_отрезков._Построение | дерева отрезков.]]
== Алгоритм построения за O(N) ==
Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. При [[Карманная сортировка | карманной сортировке]] нужно определить карман <tex>B</tex>, в который попадет текущий элемент. Затем найти число элементов в старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане <tex>B</tex>. Карман <tex>A</tex> считается старшим для кармана <tex>B</tex>, если любой элемент из <tex>A</tex> больше любого элемента из <tex>B</tex>.
'''int''' bucket_sort('''vector<int>''' permutation):
'''int''' max = число больше permutation.size и из которого можно извлечь целый квадратный корень
'''int''' bucket = sqrt(max)
'''int''' answer = 0<font color=green> // изначально кол-во инверсий</font>
'''list<list<int>>''' bank(bucket)
'''for''' i = 0 to permutation.size
'''int''' pos = (permutation[i] - 1) / (max / bucket) <font color=green>// Определяем в каком кармане должен лежать элемент</font>
'''int''' newPosition = 0
'''while''' newPosition < bank[pos].size '''and''' bank[pos][newPosition] < permutation[i] <font color=green>// идем до позиции где должен стоять элемент permutation[i] </font>
newPosition++
answer += bank[pos].size - newPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font>
bank[pos].insert(newPosition, permutation[i]) <font color=green>// вставляем элемент в Карман на свою позицию </font>
'''for''' i = position + 1 to bucket - 1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font>
answer += bank[i].size
'''return''' answer
В разделе [[Карманная сортировка | карманная сортировка]] доказывается, что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай.
Следует отметить, что хотя подсчет с помощью [[Карманная сортировка | карманной сортировки]] выполняется за линейное время, но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за <tex>O(n\log n)</tex> работает быстрее .
== Алгоритм восстановления ==
result = array(0, n)
curr = 1
'''for''' k '''in''' ls:
j = 0
'''for''' i= 0..(n- 1)
'''if''' result[i] == 0
'''if''' j == k
result = array(n)
curr = 1
'''for''' k '''in''' inv
node = tree.root
'''while''' !node.is_leaf
'''if''' k < node.left.value
node = node.left
'''else:'''
k -= node.left.value
node = node.right
