Re: some guide
- From: Mike Amling <spamonly@xxxxxxxxxxx>
- Date: 08 Feb 2007 12:48:20 EST
Timo Schneider wrote:
On 2007-02-05, shokoohcpp@xxxxxxxxxxxxxx <shokoohcpp@xxxxxxxxxxxxxx> wrote:
Hi!
describe a theta (nlog n)-time algorithm that give a set of S of n
integers
and another integer x determine wether or not there exit two elements
in s whose sum is exactly x
That sounds easy. But please keep in mind it is three o'clock in the
morning in my country, so I might be wrong.
I assume that all integers in S are positive.
1.) Sort the n elements in S with a n*log(n) sort algorithm.
Steps 2..6 seem needlessly complicated.
Let jj be the subscript of the lowest element in the sorted array.
Let kk be the subscript of the highest element.
while (jj<kk) {
if (aa[jj]+aa[kk]>x) {
--kk;
} else if (aa[jj]+aa[kk]<x) {
++jj;
} else {
break;
}
}
if (jj>=kk) {
print("Failed");
} else {
print(aa[jj] || '+' || aa[kk] || '=' x);
}
2.) Throw away everything larger than x, it's of no use.
3.) Divide the list of step 2.) in two parts:
S_1 = [0 .. x/2]
S_2 = [(x/2)+1 .. x]
Now we can look at the problem from a different angle:
Is there an s_1 \in S_1 and an s_2 \in S_2 so that s_1 + s_2 =
x? Because it can't be two elements of S_1 or S_2 that equal x,
because the sum of two members of S_1 is always smaller than x,
the sum of two members of S_2 is always bigger than x.
4.) Now we do the same thing again:
S_1 = [0 .. x/4]
S_2 = [(x/4)+1 .. x/2]
S_3 = [(x/2)+1 .. 3x/4]
S_4 = [(3x/4)+1 .. x]
Now we only have to compare the elements in S_1 two those in S_3 and
S_2 to those in S_4, this is the same problem as in Step 3.) but the
problem size is only half as big.
5.) So we get T(n) = 2*T(n/2) + c if n > 1
= 1 if n = 1
That should be O(n).
6.) O(n*log(n)) + O(n) \in O(n*log(n))
An alternative solution would be to construct some sort of lookup table
so that we can check if x_1 \in S in O(1). Then we iterate over the S
and check if x - s_i is \in S. That would be O(n).
--Mike Amling
.
- Follow-Ups:
- Re: some guide
- From: shokoohcpp@xxxxxxxxxxxxxx
- Re: some guide
- References:
- some guide
- From: shokoohcpp@xxxxxxxxxxxxxx
- Re: some guide
- From: Timo Schneider
- some guide
- Prev by Date: Re: Key entropy, stream entropy, block entropy, block population entropy AKA uniique stream length
- Next by Date: Re: working on an encrypted disk on my USB pen without admin rights: a problem without solution?
- Previous by thread: Re: some guide
- Next by thread: Re: some guide
- Index(es):
Relevant Pages
|
