Изменения

Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. Известно что карманная При [[Карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются единожды , а следовательно равномерно распределены. При | карманной сортировке ]] нужно определить карман <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> работает быстрее .