지난번에 Number of Swap Operations 글에 대해 정리했는데..

그중에 첫번째 경우 (이웃하는 경우만 swap 가능) 는 inversion 개수를 구하는 것과 같다..


구하는 방법은 전통적으로

1. bubble sort (n^2) 로 구할 수 있고

2. merge sort 를 응용해서 구할수도 있다 (nlogn)


그러나 최근에는 binary indexed tree 를 이용한 방법이 유행이다..

이와 관련하여 누군가 잘 정리해 두었다..


inversion_count_bit.pdf



'Problem Solving > Algorithm notes' 카테고리의 다른 글

Euler's phi (Totient function)  (0) 2016.08.15
The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
점과 선분과의 거리  (2) 2011.01.22
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12

to Top