Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Saturday, March 27, 2010
Number of inversions
Given an array A[0,.... n] of integer an inversion is defined as i < j and A[j] < A[i]. Suppose to randomly permute A. Give an algorithm that computes the number of inversion in A.
I can think of an algorithm whose expected/average run time is O(n lg n). Idea is that of an augment tree data structure to hold the "right tree height" of a node at any point (assuming you are putting elements with values greater than itself to the right of the Node). Now, you simply start walking thru' the array and inserting elements into the tree. If you traverse to the left of the Node, increment the "inversion counter" by that Nodes' right tree height +1 (idea is all nodes to the right of the tree were *inserted* before the current node and are greater than this node). At the end of the insertion, the count will contain the inversion index. This runs in O(n log n) average case.
I think you got the question wrong. i A[j]. This actually is an inversion isn't it?
ReplyDeletethanks made the correction
ReplyDeleteI can think of an algorithm whose expected/average run time is O(n lg n). Idea is that of an augment tree data structure to hold the "right tree height" of a node at any point (assuming you are putting elements with values greater than itself to the right of the Node). Now, you simply start walking thru' the array and inserting elements into the tree. If you traverse to the left of the Node, increment the "inversion counter" by that Nodes' right tree height +1 (idea is all nodes to the right of the tree were *inserted* before the current node and are greater than this node). At the end of the insertion, the count will contain the inversion index. This runs in O(n log n) average case.
ReplyDeleteDo an insertion sort, moving elements to the left, e.g.
ReplyDeleteEvery time you move an element to the left, there _was_ an inversion.
So: the number of inversions is the number of time you displaced the elements during insertion sort.