Article View: sci.crypt
Article #1205Random vs. exhaustive search
From: Eric Hughes
Date: Tue, 13 Oct 1992 13:59
Date: Tue, 13 Oct 1992 13:59
16 lines
1116 bytes
1116 bytes
In article <1992Oct13.115032.1@kean.ucs.mun.ca> jgarland@kean.ucs.mun.ca writes: >Also to search an entire keyspace when sampling _with_ >replacement--which is the case in at least the one implementation of >genetic algorithms that I've seen--would be inordinately >time-consuming. Incorrect. The expected time of a random search is N. The expected time of an exhaustive search is N/2. There is no upper bound on the time of a random search. The upper bound on exhaustive search is N. Hence it really only takes twice as long. See the article on the Chinese Lottery I mentioned earlier. It is exactly this argument. Eric
Technical Details
Message-ID:
<HUGHES.92Oct13135954@soda.berkeley.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!stanford.edu!agate!agate!hughesReferences:
<1992Oct13.115032.1@kean.ucs.mun.ca>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!stanford.edu!agate!agate!hughes From: hughes@soda.berkeley.edu (Eric Hughes) Newsgroups: sci.crypt Subject: Random vs. exhaustive search Date: 13 Oct 92 13:59:54 Organization: /accounts/hughes/.organization Lines: 16 Message-ID: <HUGHES.92Oct13135954@soda.berkeley.edu> References: <1992Oct13.115032.1@kean.ucs.mun.ca> NNTP-Posting-Host: soda.berkeley.edu In-reply-to: jgarland@kean.ucs.mun.ca's message of Tue, 13 Oct 1992 14:20:32 GMT