CODEWITHSUNDEEP
arraysalgorithmdata-structures
aroma
aroma

Reputation: 1421

Increase time complexity to overcome space complexity

So I have an array 'a0' of size let's say 105, and now I have to make some changes in this array. The ith change could be calculated using a function f(ai-1) to give ai in O(1) time, Where aj denotes array 'a' after jth change has been made to it. Meaning that ai could be calculated if we know ai-1 in constant time. I know that I have to make 105 changes beforehand.

Now the problem asks me to answer large number of queries such as ai[p]-aj[q], where ax[y], represents yth element of the array after xth change has been made to the array a0.

Now if I had space of the order of 1010, I could easily solve this problem in O(1) by storing all the 105 arrays beforehand but I don't (generally) have that kind of space. And I could also answer these queries by each time generating ai and aj from scratch and answering the queries but I can't afford that kind of time complexity either, so I was wondering if I could monitor this problem using some data-structure.

EDIT: Example:

We define an array B= {1,3,1,4,2,6}, and we define aj as the array storing the frequency of ith number after jth element has been added to B. That is, a0={0,0,0,0,0,0} now a1={1,0,0,0,0,0}, a2={1,0,1,0,0,0}, a3={2,0,1,0,0,0} a4={2,0,1,1,0,0} a5={2,1,1,1,0,0} and a6={2,1,1,1,0,1}.

f(aj) just adds a an element to B and updates the value of aj-1.

Upvotes: 1

Views: 175

Answers (2)

Richard
Richard

Reputation: 61389

If there is some a maximum number of states N, then checkpoints are a good way to go. For instance, if N=100,000, you might have:

c0      = [3, 5, 7, 1, ...]
c100   = [1, 4, 9, 8, ...]
c200   = [9, 7, 1, 2, ...]
...
c10000 = [1, 1, 4, 6, ...]

Now you have 1000 checkpoints. You can find the nearest checkpoint to an arbitrary state x in O(1) time and reconstruct x in at most 99 operations.

Riffing off of my comment on your question and John Zwinck's answer, if your mutating function f(*) is expensive and its effects are limited to only a few elements, then you could store the incremental changes. Doing so won't decrease the time complexity of the algorithm, but may reduce the run-time.

If you had unlimited space, you would just store all of the checkpoints. Since you do not, you'll have to balance the number of checkpoints against the incrementals appropriately. That will require some experimentation, probably centered around determining how expensive f(*) is and the extent of its effects.

Another option is to look at query behavior. If users tend to query the same or nearby locations repeatedly, you may be able to leverage an LRU (least-recently used) cache.

Upvotes: 1

John Zwinck
John Zwinck

Reputation: 249404

Assume the number of changed elements per iteration is much smaller than the total number of elements. Store an array of lists, where the list elements are (i, new_value). For example if the full view is like this:

a0 = [3, 5, 1, 9]
a1 = [3, 5, 1, 8]
a2 = [1, 5, 1, 0]

We will store this:

c0 = [(0, 3), (2, 1)]
c1 = [(0, 5)]
c2 = [(0, 1)]
c3 = [(0, 9), (1, 8), (2, 0)]

Then for the query a2[0] - a1[3], we need only consult c0 and c3 (the two columns in the query). We can use binary search to locate the necessary indexes 2 and 1 (the keys for the binary search being the first elements of the tuples).

The query time is then O(log N) for the two binary searches, where N is the maximum number of changes to a single value in the array. The space is O(L + M), where L is the length of the original array and M is the total number of changes made.

Upvotes: 2

Related Questions