Изменения
→Алгоритм построения за O(N): position -> pos, BUCKET -> bucket
Сложность представленного алгоритма есть <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> работает быстрее .
== Алгоритм восстановления ==
