число инверсий в перестанове

From

Konstantin Azarov ()

To

Gennady Mayko

Date

2003-01-07T14:50:39Z

Area

RU.ALGORITHMS

From: "Konstantin Azarov" <azarov@comtv.ru>

Hello, Gennady!

 GM> Каким образом можно узнать число инверсий в заданной перестановке,
 GM> чтобы определить, четная эта перестановка или нечетная?

 GM> Я знаю (и использую сейчас) способ, основанный на прямом подсчете
 GM> инверсий пар чисел в перестановке, но мне он кажется неэффективным.

Можно посчитать за O(n*log(n)) - надо быструю сортировку провести, попутно
подсчитывая перестановки

--- ifmail v.2.15dev5
 * Origin: Comcor-TV (2:5020/400)