Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Re: largest number inside array/hash

by TomDLux (Vicar)
on Apr 07, 2004 at 07:35 UTC ( [id://343209]=note: print w/replies, xml ) Need Help??


in reply to Re: largest number inside array/hash
in thread largest number inside array/hash

Think back to second year of college, when you took that Algorithms course.

A good sort such as quick sort is O( N logN ), poor ones such as bubble sort are O( N^2 ). A max() function requires a single pass through the list, and so is O( N ). It would be silly to do N log N - N ( i.e. N (log N - 1) ) operations more than you need to.

--
TTTATCGGTCGTTATATAGATGTTTGCA

  • Comment on Re: Re: largest number inside array/hash

Replies are listed 'Best First'.
Re: Re: Re: largest number inside array/hash
by tilly (Archbishop) on Apr 08, 2004 at 05:31 UTC
    In practice, on small data sets, the penalty is a factor of 10 or so. Which is similar to the penalty from using Perl. If you can get a good constant, the log(n) might be paid for. (Real example. Wavelet algorithms tend to be O(n) while the FFT is O(n*log(n)). But the FFT has a better constant.) At some point worrying about how the computer spends a millisecond of time itself becomes silly.

    Me, I tend to treat logarithmic factors as noise unless I'm trying to squeeze performance. The difference between linear and quadratic I care about. O(n) vs O(n*log(n)) I don't. I know them, I just don't care much.

[reply]

In Section Seekers of Perl Wisdom

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://343209]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2024-04-16 09:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found