CODEWITHSUNDEEP
algorithmdynamic
Titandrake
Titandrake

Reputation: 626

Dynamic programming over interval

I'm working on an algorithms problem, and I'm hitting a wall in speeding it up.

I have a function f(i,j), where i and j are integers such that 1 <= i <= j <= n for some upper bound n. This function is already written.

Furthermore, this function satisfies the equality f(i, j) + f(j, k) = f(i, k).

I need to compute f(x, y) for many different pairs x, y. Assume n is big enough that storing f(x,y) for every possible pair x,y will take up too much space.

Is there a known algorithm for this type of question? The one I'm using right now memoizes f and tries to reduce x,y to a previously computed pair of numbers by using the equality mentioned above, but my guess is that I'm not reducing in a smart way, and it's costing me time.

Edit: Assume that f(i, j) takes time proportional to j-i when computed the naive way.

Upvotes: 4

Views: 954

Answers (3)

MissingNumber
MissingNumber

Reputation: 1182

The function satisfies the rule 

f(i, j) + f(j, k) = f(i, k)

As you say .

So modify the function to something like f(i,j) =g(j)-g(i) , where g(i)= f(1,x)

So as 

f(i,k)=g(k)-g(i)
      =g(k)-g(j)+g(j)-g(i)
      =f(j,k) + f(i,j)

So i think if you try to store all combinations of f(i,j) it is it cost you around o(n^2) space , so better you store value of g(i) values for all values of i which is of o(n) space

so when ever you need to find f(i,j) you can actually find it as g(j)-g(i) .

As

  f(i,j)= g(j)-g(i) // as we already calculated and stored the g(i) .

Upvotes: 2

blubb
blubb

Reputation: 9910

This is a solution that requires O(n) space, O(n^2) setup time and O(1) time per evaluation.

We have that f(i, j) = -f(j, i) for i <= j.

Given is f(i, k) = f(i, j) + f(j, k). Therefore, f(i, k) = f(i, j) + f(j, k) = -f(j, i) + f(j, k). In a setup phase, fix j = 1 arbitrarily. Then, compute f(1, i) for every i and store the result. This takes O(n) space and O(n^2) time: n evaluations with running times of 1, 2, 3, ..., n.

For a query f(i, k), we need two constant-time lookups for f(i, 1) and f(k, 1).

Upvotes: 0

John Dvorak
John Dvorak

Reputation: 27317

You can use an implicit tree of power-of-two-sized intervals:

  • Store f(i,i+1) for every i
  • Store f(i,i+2) for every even i
  • Store f(i,i+4) for every i divisible by four
  • ...

There will be O(log n) tables (floor(log_2(n)), to be exact), with a total size of O(n) (~2*n).

To retrieve f(i,j) where i<=j:

  • find the highest bit where i, j differ.
  • Let n be the value with this bit set, and all lower bits cleared. This guarantees the following steps will always succeed:
  • find f(i, n) by cutting off a chunk as large as possible from the right repeatedly
  • find f(n, j) by cutting off a chunk as large as possible from the left repeatedly

The retreival accesses each table at most twice, and thus runs in O(log n).

Upvotes: 6

Related Questions