Inversion Count
Problem Solving/Algorithm notes 2016. 1. 31. 22:23
지난번에 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 |