Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: An informal introduction to O(N) notation

by jryan (Vicar)
on Jan 18, 2003 at 10:04 UTC ( #227946=note: print w/ replies, xml ) Need Help??


in reply to An informal introduction to O(N) notation

It should be noted that many algorithm's O time can be reduced. For instance, many O(n^2) algorithms can be reduced to O(n log(n)) by finding a way to cut the inner loop short. A famous example is bubblesort:

# O(n^2) for my $i (0..$#a-1) { for (0..$#a-1-$i) { ($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_]) if ($a[$_+1] < $a[$_]); } } # O(n log(n)) for my $i (0..$#a-1) { # looping over already-sorted items is not needed for (0..$#a-1-$i) { ($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_]) if ($a[$_+1] < $a[$_]); } }

O(n) algorithms that involve a search via a loop can sometimes be reduced from O(n) to O(log(n)) by breaking out of the loop once a "result" is found:

# O(n) my $truestatus; foreach my $item (@list) { $truestatus = 1 if (some_condition); } # O(log(n)) my $truestatus; foreach my $item (@list) { # if some_condition is going to be valid for at least one $item in # @list, then the limit of the average runtime will approach # O(log n). if (some_condition) { $truestatus = 1; last } }

Of course, the secret is to know where to apply these optimizations, which is often harder than it seems :)


Comment on Re: An informal introduction to O(N) notation
Select or Download Code
Re: Re: An informal introduction to O(N) notation
by MarkM (Curate) on Jan 18, 2003 at 11:07 UTC

    Your bubble sort examples for O(n) and O(n log n) are the same (the first needs to be un-optimized). Also, I believe the optimized bubble sort is O(n2/2), not O(n log n).

    For your second suggestion, loops that can break out early are still O(n) in the worst case, as no guarantee can be made that all other elements will not be considered before the target element.

Re: Re: An informal introduction to O(N) notation
by fruiture (Curate) on Jan 18, 2003 at 12:24 UTC

    Sorry, but that's nonsense. If you say that searching for an element in an unsorted list becomes O(log n) if you stop searchng after you've found the element, you actually say that every element in a list is located among it's first log(n) elements, (where n is the length of the list) and everybody knows that the elements of a list reside within the whole list, that's their definition. So your assumption would be true if there existed some "a" and some "n" for which logan = n, but there is no such a.

    Btw.: O(n) does not mean that you don't stop searching a list after you've found the thing you're looking for, of course you do that, but you must expect that you have to search the whole list if the element you're looking for is the last element or not in the list.

    But you _can_ make list search O(log n) by keeping the list sorted and then doing binary search.

    --
    http://fruiture.de
Re: Re: An informal introduction to O(N) notation
by dws (Chancellor) on Jan 18, 2003 at 17:40 UTC
    It should be noted that many algorithm's O time can be reduced.

    You may be getting "best case" and "worst case" mixed up. Clever short-circuits in implementations of algorithms often increase the best case, but only if the data behaves certain ways. There are usually mixes of data that defeat the short-cuts. O() is about worst-case behavior.

Re: Re: An informal introduction to O(N) notation
by demerphq (Chancellor) on Jan 21, 2003 at 14:02 UTC
    It should be noted that many algorithm's O time can be reduced.

    True. But then it isnt the same algorithm. :-) Also care in implementation can make one version of an algorithm outperform another. For instance I think you will find that

    my $tmp; for my $i (0..$#a-1) { # looping over already-sorted items is not needed for (0..$#a-1-$i) { if ($a[$_+1] < $a[$_]) { $tmp=$a[$_]; $a[$_]=$a[$_+1]; $a[$_+1]=$tmp; } } }
    Is slightly faster than your version. :-) Its funny actually but Knuth discusses this exact issue as a justification as to why he used MIX instead of a high level programming language. People have a tendency to write code in as few characters as possible. (Perl gives an opportunity to take this way beyond reasonable so we can ignore that stuff.) However very often the constructs that take the least space for the human result in the most code being excuted. To take this further for a while I was working on implementing a bunch of the AoP algorithms in perl. Some of them are not feasable as perl doesnt allow low enough operations. I believe that you will find one of the linear search algorthms (you'd never think this would be tricky) is unimplementable in perl to be more efficient than the others (even though in MIX and assembler it is).

    Also IIRC the following minor change makes Bubblesort get even faster

    my $tmp; my $swapped; for my $i (0..$#a-1) { $swapped=0; # looping over already-sorted items is not needed for (0..$#a-1-$i) { if ($a[$_+1] < $a[$_]) { $tmp=$a[$_]; $a[$_]=$a[$_+1]; $a[$_+1]=$tmp; $swapped=1; } } last unless $swapped; }
    As it allows it to bail once the list is sorted. (Atually you could probably be clever and not use one of the extra variables, although only if undef isnt legal in the data being sorted.)

    update fixed typo in the second version. thanks jryan. :-)

    --- demerphq
    my friends call me, usually because I'm late....

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://227946]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2014-10-01 07:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (389 votes), past polls