Нахождение количества инверсий в перестановке длины $n$

[Mathusic]

Можно ли найти количество инверсий в перестановке за $O(n)$?

[Cave]

А в связи с чем вопрос такой возник? Задали, любопытно или нужен быстрый алгоритм? За $O(n\log n)$ точно делается.

[Mathusic]

Cave в сообщении #263101 писал(а):

А в связи с чем вопрос такой возник? Задали, любопытно или нужен быстрый алгоритм? За $O(n\log n)$ точно делается.

Дали знакомому. Только подсчитать нужно чётность перестановки за $O(n)$. А он пишет так, что считается
кол-во инверсий. (за $O(n)$ не выходит), так вот я и думаю что можно как-то чётность определить по-простому, а к-во инверсий - нет.

[ИСН]

Кандидат в пессимальные алгоритмы.

[Cave]

Четность перестановки можно определить из разбиения перестановки на циклы, которое очевидно делается за $O(N)$.

[Mathusic]

Cave в сообщении #263250 писал(а):

Четность перестановки можно определить из разбиения перестановки на циклы, которое очевидно делается за $O(N)$.

Да. А разбиение подстановки на независимые циклы разве не делается как раз за $O(n)$??

[Cave]

Делается. А я что написал?