Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Computationally efficient method of assessing one measure of
variation of a function

Replies: 2   Last Post: Feb 24, 2013 9:41 PM

 Messages: [ Previous | Next ]
 James Waldby Posts: 545 Registered: 1/27/11
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:

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
else:
while delta() > d: # May discard obsolete entries
tail = 1 + hmin.dex() # hmin.val() is too small
if head - tail > bk:
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.

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

Date Subject Author
2/22/13 Paul
2/23/13 William Elliot
2/24/13 James Waldby