Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
James Waldby

Posts: 356
Registered: 1/27/11
Re: Computationally efficient method of assessing one measure of
variation of a function

Posted: Feb 24, 2013 9:41 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.