2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нахождение количества инверсий в перестановке длины $n$
Сообщение17.11.2009, 23:59 
Аватара пользователя
Можно ли найти количество инверсий в перестановке за $O(n)$?

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

 
 
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение18.11.2009, 01:06 
Аватара пользователя
Cave в сообщении #263101 писал(а):
А в связи с чем вопрос такой возник? Задали, любопытно или нужен быстрый алгоритм? За $O(n\log n)$ точно делается.

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

 
 
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение18.11.2009, 01:12 
Аватара пользователя
Кандидат в пессимальные алгоритмы.

 
 
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение18.11.2009, 18:51 
Четность перестановки можно определить из разбиения перестановки на циклы, которое очевидно делается за $O(N)$.

 
 
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение21.11.2009, 23:12 
Аватара пользователя
Cave в сообщении #263250 писал(а):
Четность перестановки можно определить из разбиения перестановки на циклы, которое очевидно делается за $O(N)$.

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

 
 
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение22.11.2009, 00:46 
Делается. А я что написал?

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group