home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / numanal / 2262 < prev    next >
Encoding:
Internet Message Format  |  1992-07-21  |  1.3 KB
  1. Path: sparky!uunet!munnari.oz.au!bunyip.cc.uq.oz.au!uqcspe!cs.uq.oz.au!anthonyb
  2. From: anthonyb@cs.uq.oz.au (Anthony Bloesch)
  3. Newsgroups: sci.math.num-analysis
  4. Subject: Re: An efficient way of finding the the delta of two numbers
  5. Message-ID: <9480@uqcspe.cs.uq.oz.au>
  6. Date: 22 Jul 92 00:09:45 GMT
  7. References: <BrpsJC.5HE@cs.columbia.edu>
  8. Sender: news@cs.uq.oz.au
  9. Reply-To: anthonyb@cs.uq.oz.au
  10. Lines: 20
  11.  
  12. In <BrpsJC.5HE@cs.columbia.edu> amir@cs.columbia.edu (Amiran Eliashvili) writes:
  13.  
  14.  
  15. >Hi all:
  16.  
  17. >    I am trying to come up with an efficient way (fewest number of
  18. >iteration ) to find in a list of numbers (not sorted) two numbers
  19. >whose delta (x - y) is the least. So far I could see O(n^2) and
  20. >possibly n*log(n). Are there any kind souls out there that know of a
  21. >better methods that will improve on the above number of iterations?
  22.  
  23. Interesting problem.  I would guess the best way boils down to sorting
  24. the list and then running  through  it looking for  the number that is
  25. closest to it's successor.  Now this  can be done in  O(n log  n) time
  26. with no real memory overhead by quicksort.  But since they are numbers
  27. we can do it in O(n) time with a radix or distribution sort.  Thus you
  28. are looking at O(n) time.  It seems to me that you will not  do better
  29. than this.
  30.  
  31.                                        Anthony
  32.