Inversions
Given a sequence x1, x2, ... xn, we say that the pair 1 &le i < j &le n is an inversion if xi > xj.
Now, given a sequence sequence S = x1, x2, ... xn, how efficently can you count the total number of inversions in S?
For example, if S = 1, 5, 4, 3 then S has 3 inversions - the pairs (5, 4), (5, 3), and (4, 3).
The straightforward algorithm is the compare all pairs of elements in S, which has a O(n2) runtime.
A better algorithm is to modify the merge sort algorithm to count the inversions that it undoes while sorting S. This yields an O(nlogn) algorithm.
Is O(nlogn) the best possible? That is, is counting inversions also &Omega(nlogn)? (This is true for (comparision-based) sorting, but one does not necessarily need to sort to S to count the total number of inversions).
2 comments:
The opening of the third book in the Art of Computer Programming talks about this stuff; you should check it out.
Yeah, I bought Knuth's books back in February, but I was a cheapskate and shipped them to my parents, so I won't see them for a for more months.
Post a Comment