Aaagh! Did it without thinking. Should be O(S*N) and O(S*2N). On Sep 28, 2009 12:09 PM, "geremy condra" <debat...@gmail.com> wrote:
On Mon, Sep 28, 2009 at 9:53 AM, John Posner <jjpos...@optimum.net> wrote: > > >> If you can enumera... 1) I honestly wouldn't know, seeing as how I wasn't alive ;). 2) After a brief tube hunt, I found that the word "pessimal" is originally from biology and appears to be somewhat more ancient than HP printers, although judging by the amount of dust I've seen on their insides I wouldn't place any large sums of money on that. 3) Apologies if the nomenclature was confusing, I tend to use l rather than the more standard |L| to denote the size of a language L. To rephrase, using S instead of l: Given an efficiently enumerable language L of size S, a unique binary representation of any sentence in L of size N can be generated in at most O(L*N) time. Because binary strings of reasonable bitlengths can be compared in a single machine operation, for most practical purposes we can simply say that equality testing will be O(1). As a result, the total time of generation and comparison for *two* sentences of size N (remember that we're not concerned about two sentences of unequal length) will be O(L*2N), and is likely to be quite fast in practice. Further optimizations- especially revolving around Bloom filters if a small margin of error is acceptable and S is large- are probably possible. Geremy Condra
-- http://mail.python.org/mailman/listinfo/python-list
