2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Нахождение количества инверсий в перестановке длины $n$
Сообщение17.11.2009, 23:59 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение18.11.2009, 01:00 


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

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


14/08/09
1140
Cave в сообщении #263101 писал(а):
А в связи с чем вопрос такой возник? Задали, любопытно или нужен быстрый алгоритм? За $O(n\log n)$ точно делается.

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

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


18/05/06
13435
с Территории
Кандидат в пессимальные алгоритмы.

 Профиль  
                  
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение18.11.2009, 18:51 


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

 Профиль  
                  
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение21.11.2009, 23:12 
Аватара пользователя


14/08/09
1140
Cave в сообщении #263250 писал(а):
Четность перестановки можно определить из разбиения перестановки на циклы, которое очевидно делается за $O(N)$.

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

 Профиль  
                  
 
 Re: Нахождение количества инверсий в перестановке длины $n$
Сообщение22.11.2009, 00:46 


02/07/08
322
Делается. А я что написал?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group