On Feb 1, 2:44 pm, "Neil Cerutti" <[EMAIL PROTECTED]> wrote: > On Feb 1, 2008 8:28 AM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > > > Yours is O(n^2) and \Omega(n^2). I think mine is O(max(c, nlogn)) > > (assuming constant time access for dictionaries, but 'inside' could be > > replaced with a list) where c is the number of overlaps. I'll try to > > post a proof later (if it's true!). So if we are in a situation where > > overlaps are rare, it is in practice O(nlogn). > > Here's another contender, basically the same as yours, but spelled > without iterators. > > def overlaps(eranges): > """Determine, from a list of numbers and a +/- range of uncertainty, which > number ranges overlap each other. Return the overlapping range indexes as > a list of overlapping pairs. > > >>> sorted(overlaps(((55, 3), (20, 2), (17, 4), (60, 3)))) > [(0, 3), (1, 2)] > """ > d = [(r[0] - r[1], r[0] + r[1], i) for i, r in enumerate(eranges)] > d.sort() > rv = [] > x = 0 > while x < len(d): > minx, maxx, ix = d[x] > y = x+1 > while y < len(d): > miny, maxy, iy = d[y] > if miny < maxx: > rv.append((ix, iy) if ix < iy else (iy, ix)) > else: > break > y += 1 > x += 1 > return rv
The total number of iterations is 1+2+...+n = n(n+1)/2 (when n is the number of intervals) so this has quadratic behaviour regardless of input. See my other post for a 'detailed' analysis of my solution. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
