Here's an idea. Say we pick any element P in the 2D array A and use
it to fill in an N element array X as follows.
j = N;
for i = 1 to N do
while A(i, j) > P do
j = j - 1;
end;
X(i) = j;
end;
This algorithm needs O(N) time.
The elements of X split each row with respect to P. That is, for each
i = 1 to N,
A(i, j) <= P if 0 < j <= X(i), A(i,j) > P if X(i) < j <= N.
Now the strategy is to create two length N arrays a = [0,0,...0]; and
b = [N,N,...]. We'll maintain the invariant that a[i] < Median <= b[i]
for some i. I.e, they "bracket" the median.
We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N -
b(i) ). These tell us how many elements there are left and right of
the bracket.
Now reduce the bracket as in binary search: Guess a value P, compute
X. If L(X) >= R(X), set b = X else set a = X.
Keep guessing new P values in a way that ensures we reduce the number
of elements between a and b by some fixed fraction. If we can do
that, we'll get to 1 element in O(N log N) time.
The remaining problem is picking good P's. Certainly the first time is
easy. Just take A(N/2, N/2). This has approximately (at least) N^2/4
elements larger than it and N^2/4 smaller due to the sorted rows and
columns. This is what we need to get O(N log N) performance.
But after the first split, things get trickier. The area between a and
b takes on the shape of a slash / /, so you can't just pick a P that
moves a and b together by a fixed fraction of remaining elements.
Not to worry! You can quickly look up the (at most) N row medians in
the bracket, i.e.
{ A(i, (a[i] + b[i] + 1) / 2) | a[i]<b[i] , i = 1 to N }
and use the well known O(N) median selection algorithm to get a median
of this. This has the quality we want of being somewhere roughly in
the middle half of the remaining elements. The logic is the same as
the selection algorithm itself, but in our case the rows are pre-
sorted.
In all, each partitioning step requires O(N), and a fixed fraction
(about 1/2) of the elements will be eliminated from the bracket with
each step. Thus O(log n) steps will be needed to bring the bracket to
size 1 for an overall cost of O(N log N).
I don't doubt that there's a simpler way, but this one seems to work.
Anyone see problems?
On Nov 3, 3:41 pm, sravanreddy001 <[email protected]> wrote:
> any better solution than O(N^2) in worst case?
> How do we take advantage of sorting and find in O(N lg N)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
