Prev: Is this problem NPC?
Next: hi
From: Richard Harter on 25 Jun 2008 12:36

Suppose we have an array and that we want to find a partitioning
element that divides the elements in the array as evenly as
possible, and that we want to do this as efficiently as possible
without moving elements.

In other words we have an array A[i], i=1,...,n. We want to find
the index of a middle element without messing up the array. If n
is odd we want the median; if n is even we want either of the
middle two.

"Efficiently as possible" has two dimensions, space and time.
Ideally we want an algorithm that is O(1) in space and O(n) in
both average time and worst case time. If there is no such
animal (and I don't think there is) what is the best that we can
do for various tradeoffs.

If we allow O(n) space we can create an array of indices and use
any of the standard algorithms for O(n) time. The question is,
can we do better than that? Thus:

If we allow O(log n) space can it be done in O(n) time?
If we allow O(1) space it be done in O(n*log n) time or better?


Richard Harter, cri(a)tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
From: tchow on 25 Jun 2008 17:21
In article <48626d52.3543796(a)news.sbtc.net>,
Richard Harter <cri(a)tiac.net> wrote:
>Suppose we have an array and that we want to find a partitioning
>element that divides the elements in the array as evenly as
>possible, and that we want to do this as efficiently as possible
>without moving elements.

I don't know the exact answer to your question offhand, but the search term
"median-finding algorithm" should point you to the right body of literature.
I do know that there are some surprisingly efficient algorithms for this
problem.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Richard Harter on 25 Jun 2008 22:55
On 25 Jun 2008 21:21:05 GMT, tchow(a)lsa.umich.edu wrote:

>In article <48626d52.3543796(a)news.sbtc.net>,
>Richard Harter <cri(a)tiac.net> wrote:
>>Suppose we have an array and that we want to find a partitioning
>>element that divides the elements in the array as evenly as
>>possible, and that we want to do this as efficiently as possible
>>without moving elements.
>
>I don't know the exact answer to your question offhand, but the search term
>"median-finding algorithm" should point you to the right body of literature.
>I do know that there are some surprisingly efficient algorithms for this
>problem.

The problem is that most efficient algorithms, e.g., Hoare's
partition algorithm and the BFPRT algorithm, presuppose moving
data. The situation is this: These algorithms require O(log n)
passes; however in each pass the amount of data that must be
examined decreases geometrically. This is achieved by data moves
that concentrate the relevant data. The question at hand is what
can we do without moving the data. The best that I can see is
something that I call the butterfly algorithm which requires
O(log n) space and O(n) time (average, but worst case O(n^2)). I
suspect that there is a worst case bounded O(log n) space and
O(n) algorithm but I haven't come p with it.


Richard Harter, cri(a)tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
From: David Wagner on 26 Jun 2008 02:37
Richard Harter wrote:
>Suppose we have an array and that we want to find a partitioning
>element that divides the elements in the array as evenly as
>possible, and that we want to do this as efficiently as possible
>without moving elements.
>
>In other words we have an array A[i], i=1,...,n. We want to find
>the index of a middle element without messing up the array. If n
>is odd we want the median; if n is even we want either of the
>middle two.
[...]
>If we allow O(1) space it be done in O(n*log n) time or better?

This is probably too trivial to be of interest to you, but in the special
case where all array elements are at most poly(n) in absolute value, it
looks to me like the answer is yes. If you have a guess at the median,
you can count how many elements are smaller than your guess in O(n)
time and decide whether to increase or decrease your guess according
to whether this count is less than or greater than n/2, respectively.
Now use binary search. (Or did I overlook something?)
From: Richard Harter on 26 Jun 2008 03:50
On Thu, 26 Jun 2008 06:37:26 +0000 (UTC),
daw(a)taverner.cs.berkeley.edu (David Wagner) wrote:

>Richard Harter wrote:
>>Suppose we have an array and that we want to find a partitioning
>>element that divides the elements in the array as evenly as
>>possible, and that we want to do this as efficiently as possible
>>without moving elements.
>>
>>In other words we have an array A[i], i=1,...,n. We want to find
>>the index of a middle element without messing up the array. If n
>>is odd we want the median; if n is even we want either of the
>>middle two.
>[...]
>>If we allow O(1) space it be done in O(n*log n) time or better?
>
>This is probably too trivial to be of interest to you, but in the special
>case where all array elements are at most poly(n) in absolute value, it
>looks to me like the answer is yes. If you have a guess at the median,
>you can count how many elements are smaller than your guess in O(n)
>time and decide whether to increase or decrease your guess according
>to whether this count is less than or greater than n/2, respectively.
>Now use binary search. (Or did I overlook something?)

In this case you are right - the time would be O(n*log n) [log n
passes, scan the entire array each time]. For numeric elements
you can do better than that by computing the low order moments
and using them to get a small range of values. If the keys are
arbitrary length keys it doesn't work.

Thanks for the suggestion.


Richard Harter, cri(a)tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
 |  Next  |  Last
Pages: 1 2 3
Prev: Is this problem NPC?
Next: hi