
Re: Computationally efficient method of assessing one measure of variation of a function
Posted:
Feb 24, 2013 9:41 PM


On Fri, 22 Feb 2013 01:43:17 0800, pepstein5 wrote:
> Let N be a positive integer. Let f be a function from the nonnegative integers <= N to the reals. Let d > 0. What is a computationally efficient way of finding the largest possible k such that there exists M >=0, M + k <=N > such that abs(f(x)  f(y)) <= d for all x, y such that x and y are both >= M and <= M + k?
Rephrasing slightly, the problem is:  Given n, d, f(), where f : N > R, find the maximum value of k such that for all i, j in { m, m+1, ... m+k }, f(i)f(j) <= d. m is unconstrained except that 0 <= m and m+k <= n. 
For a lower bound on the complexity of this problem, it is easy to create examples of f() to demonstrate that it is at least O(n); that is, where every value of f() must be tested to find the value of k. For an upper bound, it is easy to solve the problem in O(n) space, O(n lg n) time, using a min heap and a max heap as suggested in the following code:
Create min and max heaps hmin, hmax Set n to len(fval), where fval is an array of function values bm = bk = head = tail = 0 hmin.push(fval[0], 0) hmax.push(fval[0], 0)
# Loop through whole array of function values, maintaining delta() <= d while True: head += 1; if head >= n: break; hmin.push(fval[head], head) hmax.push(fval[head], head)
if delta() > d: # Is fval[head] a new min or max ? if fval[head] == hmin.val(): # Test if min while delta() > d: # May discard obsolete entries tail = 1 + hmax.dex() # hmax.val() is too big hmax.pop() # discard highest entry else: while delta() > d: # May discard obsolete entries tail = 1 + hmin.dex() # hmin.val() is too small hmin.pop() # discard lowest entry if head  tail > bk: bk = head  tail bm = tail
This code is extracted from python program <http://pat7.com/js/ynp/qdo.py>. It is about 1/3 of the program. Another 1/3 defines a heap class that supplies methods push, pop, val, and dex, and the remaining 1/3 defines a data array for testing. The val() method returns the leading value (a min or max) from a heap, and the dex() method returns the index of that value. That is, val() is equal to fval[dex()]. delta() computes hmax.val()hmin.val() and at the same time deletes heap entries that have gone out of range (ie have indices less than tail). At the end, bk is 1 less than the desired value of k.
The program uses the observation that whenever head is advanced, either fval[head] is between the existing min and max values of the array section from tail to head, or else fval[head] is a new extreme. When it's a new extreme, it is a new min or a new max. If it's a new min, we pop from hmax until delta() <= d again; if it's a new max, we pop from hmin until delta() <= d again.
> I'm also interested in continuous analogies. For example [snip re continuous functions]
 jiw

