Clever Geek Handbook

Algorithm for finding a point on an infinite line in time complexity O (n)

there is a point x with an unknown position on the infinite line. The algorithm must find this point in time complexity O (n), where n is the distance between the starting point of the search s and x. The line is split in stages. Each step is the same length.

My idea was something like this:

start in s
go 1 step left
if x found { 
    terminate
 }
else {
    go 2 steps right
    if x found { 
        terminate
    }
    else {
        go 3 steps left
        ...
        ..
        .
    }
}

But this is not a seam like O (n).

Any ideas?

thank

+3


source to share


3 answers


You have discovered the correct algorithm for the task.

But this is not a seam like O (n).



This algorithm is exactly O (n) because for every value k

between 1 and n

it reads exactly twice - once to the right at position x+k*s

m and once to the left per position x-k*s

. This means the algorithm is O (2n), but since a constant factor is always eliminated in large O notations, your algorithm is O (n).

+2


source


I am guessing that for some reason this "algorithm" must "walk" from s, visiting only one location at a time, and the total time is equal to the distance traveled ... Otherwise, you would just move two points from s in both directions until one of them finds the target. (I think this is what @dasblikenlight thinks you did)

If I am reading your question correctly, then your algorithm is on the right track, but to do this in linear time, you need to increase the distance traveled in each direction exponentially as you turn.

For example, you can go right 1, left 2, right 4, left 8, right 16, etc. Each time you turn, you cross over a previously covered area and then walk the same distance again.



Let's say you finally find x by walking 2m steps in a specific direction. The total distance you talked about is at most the sum of all 2 ^ p for p = 1 ... m. This is obtained when 2 ^ (m + 1) -1.

Also, you know that x is greater than 2 ^ (m-2) away from s, because otherwise you would have found it in an earlier pass.

2 ^ (m + 1) / 2 ^ (m-2) = 8, so the total distance traveled is less than 8n, which is definitely in O (n)

0


source


think of an infinite string as an infinite array of elements and you are asked to start from an arbitrary point,

  • cross some finite distance to the d

    right and check each index, if a value is found, if declare is found SUCCESS

    and exit

    if not found before the index d

    go to step 2
  • go left to the distance 2d

    , start checking the value with currentPos-d

    only if the indices from currentPos

    to currentPos-d

    have already been marked in the previous iteration, if the value is found in any index declaration, SUCCESS

    and exit

    if not found before currentPos-2d

    , set d=2d

    goto step 3

    .
  • Walk right up to distance 2d

    , start checking the value after currentPos+d

    just the distance, since the indices from currentPos to currentPos+d

    have already been checked in the previous iteration, if the value found at any index declares SUCCESS

    and exit

    if not found before currentPos+2d

    , set d=2d

    goto step 2

    .

This way you can avoid O (nx (n-1)) and allow O (n), since you are NOT re-checking the values ​​at each iteration in steps 2 and 3 where you avoid checking the values ​​from currentPos -d and currentPos + d, then when you set d = 2d, this is where and how you reduce the complexity of the algorithm to O (n).

0


source






More articles:


All Articles