|
in the name of god
i want to write an algorithm with order O(nlg(n)) that gets a real input (x) and searches in the array with size N of real numbers to find two elements that the addition of them is x.
i say that we must compare all elements together so how it can be O(nlg(n))?
does it work if we use binary search?how ?i dont know?
valhamdolelah.
modified on Friday, October 30, 2009 3:18 AM
|
|
|
|
|
1. Sort the array in ascending order. (This is O(n lg(n)).
2. Use two integer indexes, i & j, that point to the array elements to add. The first one (i) starts at 0 (the index of the lowest number).
3. Do a binary search in the array to find the array element that is closest to x when added to the element at index 0 (j). If array [i] + array [j] == x, we're done.
4. Loop: Advance i to the next element.
5. While array [i] + array [j] > x, decrease j. If array [i] + array [j] == x, we're done.
6. When array [i] + array [j] < x, go to Step 4. When i >= j, there's no solution and we're done.
|
|
|
|
|
Alan,
With O(n lg(n)) time to sort, doesn't that use up all of the time allotted (overall time was to be O(n lg(n)))? Wouldn't a B+ tree sort speed up that somewhat to leave a little time for the combinatorial arithmetic? With a B+ tree (n-ary tree) you eliminate many wrong values instead of just two at each step as is done in a binary tree. Once the array of values was sorted, the B+ tree search would also find the correct value quicker than O(n lg(n)) as would be the case using a binary search for the second value.
Dave.
|
|
|
|
|
Big O notation is a measure of the execution time/complexity relative to the input size.
Hence, O(n log(n)) means that the complexity in whatever unit is equal to C * n * log(n) where C is a constant. If you add an extra statement to your inner loop, you're increasing C without increasing the Big O complexity.
We say it this way, because all we're trying to measure is how much longer it would take if, say, we doubled the input size. For an O(n) algorithm, doubling the input will double the complexity.
So in essence...
O(n log(n)) + O(n log(n)) = O(n log(n))
|
|
|
|
|
O(IC)
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
|
|
|
|
|
|
I understand Big O, but in this case, after the sort, for each item, you do a binary search on the array looking for a value that when added to the initial value equals some X. Anything you do to speed up this process will help more than just removing some instruction from the inner loop. You have just added another (n (n log(n))) timeslice to the inner loop, not just some constant.
Dave.
|
|
|
|
|
But you're not doing a binary search on each item. You're doing one sort and one binary search.
Think of it this way... Say the sort and the next operation were each O(n)... Obviously they wouldn't be, but as an example. Then you're doing an O(n) followed by an O(n), or 2 * O(n). But in Big O, we eliminate constants, so it simplifies to just O(n)...
If the two operations are of different complexity, we take the larger one... If it was O(n log(n)) followed by O(n), we'd say the Big O was O(n log n).
|
|
|
|
|
Ian Shlasko wrote: You're doing one sort and one binary search.
But you are not doing that, you are doing the binary search n times looking for a pair that add up to the constant X.
Dave.
|
|
|
|
|
Sorry, mixed it up a bit, but I'm still right about the complexity.
A binary search is O(log n)... And we'd be doing that n times... Hence, O(n log(n)) for all of the searches.
But this is still done AFTER the sort, not inside it, so it adds to the sort instead of multiplying with it.
|
|
|
|
|
You had it right the first time -- Only one binary search is done. It's done to find the upper bound of number pairs that could possibly add up to x.
|
|
|
|
|
I agree with your algo, however I would rephrase it in a more symmetric way, making the O(n) part more clear:
1. Sort the array in ascending order
2. let int i=0 and int j=n-1
3. if i>=j then search is over
4. calculate sum=array[i]+array[j]
5. if sum<x, increment i and goto (3)
6. if sum>x, decrement j and goto (3)
7. since sum==x, solution found (either stop; or increment i, decrement j and goto 3)
(1) is O(n ln(n))
(2)-(7) is O(n) as i and j move towards each other in steps of 1
hence overall O(n ln(n))
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
|
|
|
|
|
in the name of god<br />
hello and thanks for your answers.<br />
it is the code i wrote in c++:<br />
<br />
int main(){<br />
cin<<x;<br />
mergeSort(Arbegin,Arend);
int i=0;<br />
while(i<j){<br />
int sum=A[i]+A[j];<br />
if(x < sum){<br />
i++;<br />
}<br />
if(x < sum){<br />
j--;<br />
}<br />
if(sum==x){<br />
a=i;<br />
b=j;<br />
break;<br />
}<br />
}<br />
}<br />
valhamdolelah.
modified on Friday, October 30, 2009 8:20 AM
|
|
|
|
|
Lets say I'm standing on a matrix and
1. There are obstacles where I cant stand
2. There is a goal in some x,y
3. I only know the content of the 8 adjacent points
4. I need to return one move based on the one i'm standing each time.
Any ideas on the algorithm for returning my move each time?
I'm more interested in the correctiness rather than the efectiveness
|
|
|
|
|
Follow an expanding spiral from your starting position. When you encounter am obstacle, circle around it in the same direction (clockwise/counter~) as your spiral.
|
|
|
|
|
Nice idea, hadnt thought about spirals.., thanks.
Though "circle around an obstacle" its not that simple because there might be several obstacles one each to the other, making a kind of wall.. for example
########
#
goal # me
#####
#
#
|
|
|
|
|
Treat several obstacles as one big obstacle, and make a bigger circle.
One way to do this is with a direction vector, the pair of x,y offsets in the direction of your spiral. When you hit an obstacle, you rotate this direction vector 90 degrees (45 degrees if diagonal moves are permitted). When you find a free cell around the obstacle, you rotate back in the other direction.
Intuitively, it's like going through a maze, always keeping your right hand on the right wall, as you circle around obstacles.
|
|
|
|
|
"several obstacles as one obstacle" makes me consider using Disjoint Sets..
|
|
|
|
|
You may be making it more complex than it needs to be. If you were feeling your way through a maze in the dark with your right hand on the right wall, you'd just keep going straight until you hit an obstacle. Then since you couldn't continue in the same direction, you'd rotate your direction vector 45 degrees to the left. If that direction was free you'd advance, else you'd rotate again.
|
|
|
|
|
For this particular problem, you may also want to store the coordinates of the spiral you've already traversed, so that you take up where you left off once you've circled around obstacles.
|
|
|
|
|
Any ideas for a "contour follow" algorithm?
Like "contour follow with left hand on wall" and "countour follow with right hand on wall"
|
|
|
|
|
A potentials approach and you make a walk through the troughs.. again Probably more work then you really need. (and a lot of floating point calculations)
|
|
|
|
|
In general, rotate your direction vector right at each step, and when you hit an obstacle rotate left.
With your right hand on the wall, you try to rotate right (into the wall) at each step. Since you can't go into the wall, you then rotate left, and your resulting path is a straight line along the wall.
If you come to a corner, when you rotate right you turn right, which takes you around the corner.
If you come to an obstacle, rotating right doesn't work, so you rotate left (aiming straight ahead). Since there's an obstacle, going straight doesn't work, so you rotate left again. If that path is clear, you proceed in that direction (left from your original direction). If that path is also blocked (a dead end), you rotate left again (facing backwards) and advance back the way you came.
|
|
|
|
|
I replied you, look my reply :P
|
|
|
|
|
P.S. After you've found the goal, you can optimize the path as follows:
If a coordinate appears twice in your path, delete all the moves from after the first time the coordinate is reached, up to and including the last time that same coordinate is reached.
This eliminates any backtracking that was done.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
