home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3759 < prev    next >
Encoding:
Internet Message Format  |  1992-10-13  |  1.1 KB
  1. Path: sparky!uunet!stanford.edu!agate!agate!hughes
  2. From: hughes@soda.berkeley.edu (Eric Hughes)
  3. Newsgroups: sci.crypt
  4. Subject: Random vs. exhaustive search
  5. Date: 13 Oct 92 13:59:54
  6. Organization: /accounts/hughes/.organization
  7. Lines: 16
  8. Message-ID: <HUGHES.92Oct13135954@soda.berkeley.edu>
  9. References: <1992Oct13.115032.1@kean.ucs.mun.ca>
  10. NNTP-Posting-Host: soda.berkeley.edu
  11. In-reply-to: jgarland@kean.ucs.mun.ca's message of Tue, 13 Oct 1992 14:20:32 GMT
  12.  
  13. In article <1992Oct13.115032.1@kean.ucs.mun.ca>
  14. jgarland@kean.ucs.mun.ca writes:
  15.  
  16. >Also to search an entire keyspace when sampling _with_
  17. >replacement--which is the case in at least the one implementation of
  18. >genetic algorithms that I've seen--would be inordinately
  19. >time-consuming.
  20.  
  21. Incorrect.  The expected time of a random search is N.  The expected
  22. time of an exhaustive search is N/2.  There is no upper bound on the
  23. time of a random search.  The upper bound on exhaustive search is N.
  24.  
  25. Hence it really only takes twice as long.  See the article on the
  26. Chinese Lottery I mentioned earlier.  It is exactly this argument.
  27.  
  28. Eric
  29.