Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #41179

Re: Finding the Min for positive and negative in python 3.3 list

Show all headers | View raw

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.maier@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Finding the Min for positive and negative in python 3.3 list Norah Jones <nh.jones01@gmail.com> - 2013-03-12 17:03 +0000
  Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 01:57 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 10:43 +0000
      Re: Finding the Min for positive and negative in python 3.3 list 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-14 04:45 -0700
      Re: Finding the Min for positive and negative in python 3.3 list 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-14 04:45 -0700
    Re: Finding the Min for positive and negative in python 3.3 list Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-03-13 11:23 +0000
      Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 14:12 +0000
        Re: Finding the Min for positive and negative in python 3.3 list Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-03-13 14:37 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 11:34 +0000
      Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 14:43 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Chris Angelico <rosuav@gmail.com> - 2013-03-13 22:36 +1100
    Re: Finding the Min for positive and negative in python 3.3 list Chris Angelico <rosuav@gmail.com> - 2013-03-13 22:38 +1100
    Re: Finding the Min for positive and negative in python 3.3 list Peter Otten <__peter__@web.de> - 2013-03-13 13:00 +0100
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 14:17 +0000

csiph-web