Изменения

Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой. Известно что карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются единожды , а следовательно равномерно распределены]]. При карманной сортировке нужно определить карман <tex>B</tex>, в который попадет текущий элемент. Затем найти количество элементов в старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане <tex>B</tex>. Карман <tex>A</tex> считается старшим для кармана <tex>B</tex>, если любой элемент из <tex>A</tex> больше любого элемента из <tex>B</tex>.

<font color=green>MAX - число больше a.size и из которого можно извлечь целый квадратный корень.</font> <font color=green>BUCKET - размер кармана BUCKET=sqrt(MAX)</font> '''int''' bucket_sort('''vector<int>''' aPermutation): MAX = число больше Permutation.size и из которого можно извлечь целый квадратный корень BUCKET=sqrt(MAX) '''int''' ans Answer = 0<font color=green> // изначально кол-во инверсий</font> '''vector<int>''' tab_inversTabInvers(aPermutation.size + 1) <font color=green>// таблица перестановок</font> '''vector< listvector<int> >''' memBank(BUCKET) '''for'''('''int''' i = 0;i < ato Permutation.size ; i++) '''int''' invers Invers = 0 <font color=green> // кол-во инверсий которые создает элемент a[i]</font> '''int''' pos Position = (aPermutation[i] - 1)/(MAX / BUCKET) <font color=green>// Определяем в каком кармане должен лежать элемент</font> '''list<int>::iterator''' it = mem[pos]'''.begin()''' '''int''' newpos NewPosition = 0 '''while'''(it != memNewPosition < Bank[pos]'''.end()''' size && (*it) Bank[pos][NewPosition] < aPermutation[i] ) <font color=green>// идем до позиции где должен стоять элементPermutation[i] </font> it++ newposNewPosition++ invers Invers += memBank[pos].size - newpos NewPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font> memBank[pos]'''.insert'''( it NewPosition , aPermutation[i] ) <font color=green>// вставляем элемент в списокКарман на свою позицию </font> '''for'''('''int''' i = pos Position + 1 ; i < to BUCKET ; i++) -1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font> invers Invers += memBank[i].size tab_inversTabInvers[aPermutation[i]] = inversInvers ans Answer += inversInvers '''return''' ansAnswer Известно что карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются на отрезке от <tex>[1;n]</tex> единожды , а следовательно равномерно распределены.