"Anton Vredegoor" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] | Terry Reedy wrote: | | > One could generate the items in order in less space by doing, for instance, | > an m-way merge, in which only the lowest member of each of the m sublists | > is present at any one time. But I don't know if this (which is | > O(m*n*log(m))) would be any faster (in some Python implementation) for any | > particular values of m and m. | | If hashing is O(n+m), it would mean that it would be faster. | | I'm not sure if I can agree with your analysis. All information to | generate the product is already inside the two lists we begin with. | Doesn't that make the product less complex than a random n*m matrix? Or | is that what you are saying with O(m*n*log(m)) ?
If I understand correctly, you want to multiiply each of m numbers by each of n numbers, giving m*n products. That is O(m*n) work. Inserting (and extracting) each of these is a constant size m priority cue takes, I believe, O(log(m)) work, for a total of m*n*log(m). That is faster than O(m*n*log(m*n)) for sorting m*n random numbers. I don't know how you would sort by hashing. Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
