On 13/03/2013 14:12, Steven D'Aprano wrote:
On Wed, 13 Mar 2013 11:23:22 +0000, Oscar Benjamin wrote:
On 13 March 2013 10:43, Wolfgang Maier
<wolfgang.ma...@biologie.uni-freiburg.de> wrote:
thinking again about the question, then the min() solutions suggested
so far certainly do the job and they are easy to understand. However,
if you need to run the function repeatedly on larger lists, using min()
is suboptimal because its performance is an O(n) one. It's faster,
though less intuitive, to sort your list first, then use bisect on it
to find the zero position in it. Two manipulations running at
O(log(n)).
Sort cannot be O(log(n)) and it cannot be faster than a standard O(n)
minimum finding algorithm. No valid sorting algorithm can have even a
best case performance that is better than O(n). This is because it takes
O(n) just to verify that a list is sorted.
That's almost true. It applies to comparison sorts, that is, the kind of
sort algorithm where you have to compare the elements being sorted to
know where they go. But it doesn't necessarily apply to non-comparison
sorts. For example, Bead sort could in principle operate in O(sqrt(n))
time, or even O(1), although in practice it is O(n).
Another example is Bitonic sort, which is O(log(n)**2).
In practical terms though, you are right. There is no practical, general
purpose sorting algorithm that can beat O(n) for arbitrary lists of data.
For the newbies hanging around there's Python's own Timsort which
apparantly has worst case performance O(n log n), best case O(n) and
average case O(n log n). Please don't shoot the messenger :)
--
Cheers.
Mark Lawrence
--
http://mail.python.org/mailman/listinfo/python-list
